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

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

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

Якщо така функція $f$ існує, кажуть, що $L_{1}$ звідна за Карпом до $L_{2}$ і пишуть

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

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

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

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

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

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

Див. також

• Зведення

Посилання

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