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

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

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

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

$L_1{⩽<!--\; ⩽\; -->}_K{L}_2.$$L_{1}\leqslant _{K}L_{2}.$

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

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

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

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

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

См. такжеПравить

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

СсылкиПравить

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