Русская Википедия:Полиномиальная сводимость

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Любой язык <math>L_1</math> называется сводимым по Карпу к языку <math>L_2</math>, если существует функция <math>F\colon \Sigma^* \mapsto \Sigma^*</math>, вычисляемая за полиномиальное время, где F(x) принадлежит <math>L_2</math> в том случае, если x принадлежит <math>L_1</math>. Язык называется NP-трудным, если к нему сводится любой язык NP класса, и называется NP-полным, если он NP-труден и сам сводится к NP классу. Если будет алгоритм, решающий NP-полную задачу за полиномиальное время, тогда все NP-задачи относятся к классу P.

Рассмотрим два языка <math>L_1</math> и <math>L_2</math> над алфавитами <math>\Sigma</math> и <math>\Gamma</math>. Сведение <math>L_1</math> к <math>L_2</math> по Карпу — это функция <math>f\colon \Sigma^* \mapsto \Gamma^*</math>, вычислимая за полиномиальное время, такая, что <math>\forall x (x \in L_1 \Leftrightarrow f(x) \in L_2)</math>. Таким образом, неформально язык <math>L_1</math> «не сложнее» языка <math>L_2</math>.

Если такая функция <math>f</math> существует, говорят, что <math>L_1</math> сводима по Карпу к <math>L_2</math> и пишут

<math>L_1 \leqslant_K L_2.</math>

Отметим, что сведение по Карпу является частным случаем сведения по Куку. В англоязычных источниках также можно встретить название en:many-one reduction.

Класс языков PSPACE — множество языков, допустимых детерминированной машиной Тьюринга с полиномиальным ограничением пространства.

Класс языков NPSPACE — множество языков, допустимых недетерминированной машиной Тьюринга с полиномиальным ограничением пространства.

Транзитивность

Главным свойством сведение по Карпу является транзитивность. Если представить языки в виде символов, то можно рассматривать как математическую операцию: Α>Β, Β>Ε → Α>Ε.

См. также

• Понятие сведения. Список.

Ссылки

• Курс «Введение в структурную теорию сложности»
• Хопкфрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений, 2-е изд.: Пер. с англ. — М.: Издательский дом «Вильямс», 2002.
• М. Н. Вялый, Сложность вычислительных задач Шаблон:Wayback — определение на функциях, без понятий «язык», «алфавит» и т. п.