Полиномиальная сводимость

Любой язык ${\displaystyle L_{1}}$ называется сводимым по Карпу к языку ${\displaystyle L_{2}}$, если существует функция ${\displaystyle F\colon \Sigma ^{*}\mapsto \Sigma ^{*}}$, вычисляемая за полиномиальное время, где F(x) принадлежит ${\displaystyle L_{2}}$ в том случае, если x принадлежит ${\displaystyle L_{1}}$. Язык называется NP-трудным, если к нему сводится любой язык NP класса, и называется NP-полным, если он NP-труден и сам сводится к NP классу. Если будет алгоритм, решающий NP-полную задачу за полиномиальное время, тогда все NP-задачи относятся к классу P.

Рассмотрим два языка ${\displaystyle L_{1}}$ и ${\displaystyle L_{2}}$ над алфавитами ${\displaystyle \Sigma }$ и ${\displaystyle \Gamma }$. Сведение ${\displaystyle L_{1}}$ к ${\displaystyle L_{2}}$ по Карпу — это функция ${\displaystyle f\colon \Sigma ^{*}\mapsto \Gamma ^{*}}$, вычислимая за полиномиальное время, такая, что ${\displaystyle \forall x(x\in L_{1}\Leftrightarrow f(x)\in L_{2})}$. Таким образом, неформально язык ${\displaystyle L_{1}}$ «не сложнее» языка ${\displaystyle L_{2}}$.

Если такая функция ${\displaystyle f}$ существует, говорят, что ${\displaystyle L_{1}}$ сводима по Карпу к ${\displaystyle L_{2}}$ и пишут

${\displaystyle L_{1}\leqslant _{K}L_{2}.}$

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

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

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

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

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

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