Главная arrow книги arrow Копия Приложение А. Математические основы arrow Изначально сложные и недетерминированные полиномиальные задачи
Изначально сложные и недетерминированные полиномиальные задачи

Ученые, пытающиеся найти ответ на вопрос о том, эквивалентны ли классы Ρ и ΝΡ, выделили подкласс класса ΝΡ, называемый NP-полными задачами. В этой формулировке слово "полный" означает "являющийся наиболее ярким представителем" и поэтому указывает на самые трудные задачи из класса ΝΡ. Было доказано, что либо все NP-полные задачи принадлежат к классу Р, либо ни одна из них к нему не относится. Таким образом, данный класс представляет определенный теоретический интерес, но он важен также с точки зрения практики, поскольку известно, что многие серьезные задачи являются NP-полными. В качестве примера можно указать задачу установления выполнимости: если дано высказывание пропозициональной логики, то есть ли такой вариант присваивания истинностных значений пропозициональным символам в высказывании, при котором оно становится истинным? Если не произойдет чудо и не совпадут друг с другом классы Р и NP, то нельзя будет найти алгоритм, который позволяет решить все задачи установления выполнимости за полиномиальное время. Но исследователей в области искусственного интеллекта в большей степени интересует то, существуют ли алгоритмы, действующие достаточно эффективно при решении типичных задач, выбранных с помощью заранее заданного распределения; как было показано в главе 7, существуют алгоритмы наподобие WalkSAT, которые действуют вполне успешно при решении многих задач.

Класс ко-NP является комплементарным (дополнительным) по отношению к классу NP; это означает, что для каждой задачи принятия решения из класса NP существует соответствующая задача в классе ко-NP, на которую может быть дан положительный или отрицательный ответ, противоположный ответу на задачу класса NP. Известно, что Р является подмножеством и NP, и ко-NP, кроме того, считается, что к классу ко-NP относятся некоторые задачи, не входящие в класс Р. Такие задачи называются ko-NP-полными и являются самыми трудными задачами в классе ко-NP.