Полиномиальная сводимость (трансформируемость)

Материал из WikiGrapp
Перейти к:навигация, поиск

Полиномиальная сводимость (трансформируемость) (Polinomial transformation) — Язык \,L называется полиномиально сводимым (трансформируемым) к \,L_0, если некоторая машина Тьюринга с полиномиальной временной сложностью \,M преобразует каждую цепочку \,\omega в алфавите языка \,L в такую цепочку \,\omega_0 в алфавите языка \,L_0 (т.е. \,M, обрабатывая цепочку \,\omega, достигает заключительной конфигурации, в которой \,\omega_0 — непустая часть ее ленты), что \,\omega\in L тогда и только тогда, когда \,\omega_0\in L_0.

Отношение полиномиальной сводимости обладает свойством транзитивности. Поэтому, если уже известна {\mathcal NP}-полнота одной из задач (одного из языков), то процедура доказательства {\mathcal NP}-полноты других задач (языков) может быть существенно упрощена. Для доказательства {\mathcal NP}-полноты задачи P \in {\mathcal NP} достаточно показать, что какая-нибудь из известных {\mathcal NP}-полных задач \,P' может быть сведена к \,P. Таким образом, процесс доказательства {\mathcal NP}-полноты задачи \,P может состоять из следующих четырех шагов:

(1) доказательства, что P \in {\mathcal NP};

(2) выбора подходящей известной {\mathcal NP}-полной задачи \,P';

(3) построения функции \,f, сводящей задачу \,P' к задаче \,P;

(4) доказательства того, что функция \,f осуществляет полиномиальное сведение.

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.