Задача о выполнимости

Булево выражение называется выполнимым, если существует хотя бы одна комбинация значений переменных, подстановка которых обращает его в единицу.

Пример. □ Выражение выполнимо, так как при это выражение обращается в единицу. Выражение не является выполнимым, поскольку на всех наборах переменных оно равно нулю. ■

Задача о выполнимости состоит в том, чтобы установить, выполнимо ли некоторое булево выражение, представленное в конъюнктивной нормальной форме.

Справедливо следующее утверждение.

Теорема. Задача о выполнимости является NP – полной.

Задачу коммивояжера удается решить за время, экспоненциально зависящее от числа городов. Таким образом, задача коммивояжера принадлежит к числу NP – полных.

Определение того, имеет ли ориентированный или неориентированный граф гамильтонов цикл есть NP – полная задача.

Определение оптимального маршрута в задаче коммивояжера с симметричной матрицей стоимостей является NP – полной задачей.