Reductibilitate polinomială

Se spune că orice limbaj este Karp reductibil la o limbă dacă există o funcție care poate fi calculată în timp polinomial, unde F(x) aparține dacă x aparține lui . Un limbaj se numește NP-hard dacă orice limbă dintr-o clasă NP este reductibilă la el și se numește NP-complet dacă este NP-hard și este ea însăși reductibilă la o clasă NP. Dacă există un algoritm care rezolvă o problemă NP-completă în timp polinomial, atunci toate NP-problemele aparțin clasei P. $L_{1}$ $L_{2}$ $F\colon \Sigma ^{*}\mapsto \Sigma ^{*}$ $L_{2}$ $L_{1}$

Luați în considerare două limbi și peste alfabete și . Reducerea Karp la este o funcție care poate fi calculată în timp polinomial astfel încât . Astfel, în mod informal, limbajul nu este „mai dificil” decât limbajul . $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}$

Dacă o astfel de funcție există, spunem că este Karp reductibilă la și scrieți $f$ $L_{1}$ $L_{2}$

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

Rețineți că reducerea Karp este un caz special al reducerii Cook . În sursele în limba engleză, puteți găsi și numele en:many-one reduction .

Clasa de limbaj PSPACE este setul de limbaje permise de o mașină Turing deterministă cu o constrângere de spațiu polinomial.

Clasa de limbaj NPSPACE este setul de limbaje permis de o mașină Turing nedeterministă cu o constrângere de spațiu polinomial.

Tranzitivitate

Principala proprietate a reducerii Karp este tranzitivitatea. Dacă limbile sunt reprezentate ca simboluri, atunci poate fi considerată o operație matematică: Α>Β, Β>Ε → Α>Ε.

Vezi și

Conceptul de informare. Listă.

Link -uri

Curs „Introducere în teoria complexității structurale”
Hopkfroft J., Motwani R., Ulman J. Introducere în teoria automatelor, limbajelor și calculului, ed. a II-a: Per. din engleza. - M .: Editura Williams, 2002.
M. N. Vyaly, Complexitatea problemelor de calcul