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

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

Рассмотрим два языка L 1 {displaystyle L_{1}} и L 2 {displaystyle L_{2}} над алфавитами Σ {displaystyle Sigma } и Γ {displaystyle Gamma } . Сведение L 1 {displaystyle L_{1}} к L 2 {displaystyle L_{2}} по Карпу — это функция f : Σ ∗ ↦ Γ ∗ {displaystyle fcolon Sigma ^{*}mapsto Gamma ^{*}} , вычислимая за полиномиальное время, такая, что ∀ x ( x ∈ L 1 ⇔ f ( x ) ∈ L 2 ) {displaystyle forall x(xin L_{1}Leftrightarrow f(x)in L_{2})} . Таким образом, неформально язык L 1 {displaystyle L_{1}} «не сложнее» языка L 2 {displaystyle L_{2}} .

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

L 1 ⩽ K L 2 . {displaystyle L_{1}leqslant _{K}L_{2}.}

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

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

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

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

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