Поліноміальна звідність

Будь-яка мова ${\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}.}$

Відзначимо, що зведення за Карпом є окремим випадком зведення за Куком. У англомовних джерелах також можна зустріти назву many-one reduction.

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

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