Структуры данных и модели вычислений

         

если существуют работающие полиномиальное время


Задача полиномиально сводится к задаче , если существуют работающие полиномиальное время тьюринговы программы и такие, что

Из этого определения следует, что для решения задачи на входе достаточно

  • вычислить ,
  • затем найти ответ задачи на входе ,
  • и, наконец, применить к программу , получив ответ задачи на входе .


Таким образом, имеем следующую схему получения ответа :

Оказывается, что среди задач с полиномиально проверяемым ответом существует задача, к которой полиномиально сводится любая другая задача с полиномиально проверяемым ответом. Такие задачи получили название универсальных переборных задач.

Исторически существование универсальных переборных задач обнаружено в 1971 году американским математиком C.A.Куком, когда он доказал, что задача выполнимости булевой формулы является универсальной переборной задачей. Тогда же было доказано, что и многие другие широко известные задачи являются универсальными переборными задачами.

Круг таких задач в настоящее время постоянно расширяется. По данному вопросу имеется обширная литература[3].


Содержание  Назад  Вперед