О задаче ВЫПОЛНИМОСТЬ

Вопрос. Недавно услышал следующую информацию относительно задачи ВЫПОЛНИМОСТЬ. Якобы разработан алгоритм, позволяющий свести исходную формулу 3-ВЫП к виду, в котором она представлена в виде двух структур, определенных на общих переменных. И для каждой из структур может быть найдено решение за полиномиальное время. То есть решение исходной задачи заключается в нахождении пересечения множеств выполняющих наборов обеих структур.

Известно ли что-либо про это? Также с удовольствием бы послушал обзор про современное состояние в данной области.

Ответ. Редакция не смогла ответить на этот вопрос. Не ясна формулировка. Что такое структура? Что такое решение структуры? При различных интерпретациях этих терминов получается широкий спектр утверждений, от тривиальных до сенсационных ($\mathrm{P}=\mathrm{NP}$).

Что касается второй части вопроса… Мы бы тоже почитали хороший обзор по задаче ВЫПОЛНИМОСТЬ. Дело в том, что последняя — бесспорно самая популярная из вычислительных задач. Проводится ежегодная международная конференция, издается журнал, поддерживается некоторое количество сайтов, из которых, вероятно, наиболее известным является SAT-LIVE! И это только специализированные источники информации, посвященные задаче ВЫПОЛНИМОСТЬ. Кроме того, ежегодно проводятся соревнования среди программ (SAT-solvers), решающих эту задачу. А “краткий” обзор состояния исследований задачи ВЫПОЛНИМОСТЬ представляет собой почти 1000-страничную монографию. Справедливости ради, следует отметить, что тематика этой книги на самом деле несколько шире (SAT, 3-SAT, k-SAT, CSP…).

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна