Вадим Владиславович Лозин (Университет Ворвика, Великобритания) сделает доклад на семинаре лаборатории

Задачи о клике, раскраске и выполнимости - три центральных задачи теоретической информатики. Все эти задачи в общем случае NP-трудные. С другой стороны, каждая из них может стать полиномиально разрешимой при рассмотрении входных объектов определенной структуры. В этом докладе исследуется вопрос о том, как структура входных данных может влиять на вычислительную сложность этих задач. Также обсуждаются некоторые алгоритмические средства для решения рассматриваемыхзадач. Особое внимание уделяется преобразованиям графов и конъюнктивных нормальных форм (КНФ).