Структуры данных и модели вычислений
если существуют работающие полиномиальное время
Задача полиномиально сводится к задаче , если существуют работающие полиномиальное время тьюринговы программы и такие, что
Из этого определения следует, что для решения задачи на входе достаточно
- вычислить ,
- затем найти ответ задачи на входе ,
- и, наконец, применить к программу , получив ответ задачи на входе .
Таким образом, имеем следующую схему получения ответа :
Оказывается, что среди задач с полиномиально проверяемым ответом существует задача, к которой полиномиально сводится любая другая задача с полиномиально проверяемым ответом. Такие задачи получили название универсальных переборных задач.
Исторически существование универсальных переборных задач обнаружено в 1971 году американским математиком C.A.Куком, когда он доказал, что задача выполнимости булевой формулы является универсальной переборной задачей. Тогда же было доказано, что и многие другие широко известные задачи являются универсальными переборными задачами.
Круг таких задач в настоящее время постоянно расширяется. По данному вопросу имеется обширная литература[3].
