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

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

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

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

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

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

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

Див. також

• Зведення

Посилання

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