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

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

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

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

$L_1{⩽}_K{L}_2.$

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

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

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

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

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

Див. також

• Зведення

Посилання

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