Polinomiális redukálhatóság

Bármely nyelvet Karp nyelvre redukálhatónak mondjuk, ha létezik olyan függvény , amely polinomiális időben kiszámítható, ahol F(x) akkor tartozik , ha x tartozik . Egy nyelvet NP-keménynek nevezünk, ha egy NP-osztály bármely nyelve visszavezethető rá, és NP-teljesnek nevezzük, ha NP-kemény, és maga is redukálható NP-osztályra. Ha van olyan algoritmus, amely egy NP-teljes feladatot polinomiális időben old meg, akkor az összes NP-probléma a P osztályba tartozik. $L_{1}$ $L_{2}$ $F\colon \Sigma ^{*}\mapsto \Sigma ^{*}$ $L_{2}$ $L_{1}$

Vegyünk két nyelvet és az ábécét és a . A Karp - redukció egy olyan függvény, amely polinomiális időben számítható úgy, hogy . Így informálisan a nyelv „nem nehezebb”, mint a nyelv . $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}$

Ha létezik ilyen függvény , azt mondjuk, hogy Karp- ra redukálható és írható $f$ $L_{1}$ $L_{2}$

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

Vegye figyelembe, hogy a Karp-csökkentés a Cook-csökkentés speciális esete . Az angol forrásokban az en:many-one redukció elnevezés is megtalálható .

A PSPACE nyelvosztály azon nyelvek halmaza, amelyeket egy determinisztikus Turing-gép engedélyez polinomiális térkényszerrel.

Az NPSPACE nyelvosztály azon nyelvek halmaza, amelyeket egy nemdeterminisztikus Turing-gép polinomiális térkényszerrel engedélyez.

Tranzitivitás

A Karp redukció fő tulajdonsága a tranzitivitás. Ha a nyelveket szimbólumokként ábrázoljuk, akkor ez matematikai műveletnek tekinthető: Α>Β, Β>Ε → Α>Ε.

Lásd még

Az információ fogalma. Lista.

Linkek

"Bevezetés a strukturális komplexitás elméletébe" tanfolyam
Hopkfroft J., Motwani R., Ulman J. Bevezetés az automaták, nyelvek és számítástechnika elméletébe, 2. kiadás: Per. angolról. - M .: Williams Kiadó, 2002.
M. N. Vyaly: A számítási problémák összetettsége