В задаче о гомоморфизме графов на вход подается два графа и требуется узнать, существует ли отображение вершин одного в вершины другого, которое переводит ребра в ребра. Задача о гомоморфизме графов обобщают задачу о раскраске графа, для которой не так давно был придуман относительно быстрый алгоритм со сложностью O*(2^n). За последние годы было предпринято несколько попыток адаптировать этот алгоритм (или придумать другой) для задачи о гомоморфизме, однако удовлетворительные результаты были получены только для частных случаев. В докладе будет показано, почему создание эффективного алгоритма для этой задачи противоречит ETH - популярной гипотезе о том, что для 3-SAT не существует алгоритма с субэкспоненциальным временем работы.