NP (complexitate)

Diagrama Euler-Venn pentru clasele de complexitate P , NP, NP-complete și NP-hard

Clasa problemelor $N\!P$ ${\ displaystyle N \! P}$ ${\ displaystyle N \! P}$ include toate acele probleme de luare a deciziilor care, pentru a găsi o soluție pe o mașină Turing nedeterministă, necesită un timp polinomial. Clasa NP își ia numele din abrevierea pentru Timp polinom nedeterminist .

Clasa $N\!P$ ${\ displaystyle N \! P}$ ${\ displaystyle N \! P}$ poate fi definit într-un mod alternativ prin exploatarea mașinilor Turing nedeterministe . De fapt, veți primi acest lucru $S.$ ${\ displaystyle S}$ $S.$ ca un set de cuvinte pe un alfabet $LA$ ${\ displaystyle A}$ $LA$ , asa de $S.$ ${\ displaystyle S}$ $S.$ este în clasă $N\!P$ ${\ displaystyle N \! P}$ ${\ displaystyle N \! P}$ dacă și numai dacă există o mașină Turing nedeterministă de complexitate polinomială $M.$ ${\ displaystyle M}$ $M.$ care, pentru fiecare intrare $w\in S$ ${\ displaystyle w \ in S}$ $w \ in S$ , are cel puțin un calcul care converge.

Pe scurt $S\in N\!P$ ${\ displaystyle S \ in N \! P}$ ${\ displaystyle S \ in N \! P}$ dacă există o mașină Turing nedeterministă care acceptă $S.$ ${\ displaystyle S}$ $S.$ (deci converge pentru fiecare intrare $w\in S$ ${\ displaystyle w \ in S}$ $w \ in S$ ).

Luând o mașină Turing nedeterministă de complexitate polinomială, atunci va accepta un limbaj $S.$ ${\ displaystyle S}$ $S.$ care va fi o problemă care aparține clasei $N\!P$ ${\ displaystyle N \! P}$ ${\ displaystyle N \! P}$ . Prin urmare, o astfel de mașină Turing, pentru fiecare intrare $w\in S$ ${\ displaystyle w \ in S}$ $w \ in S$ va avea printre toate calculele posibile pe această intrare, unul care se oprește.

În schimb, dacă intrarea $w$ ${\ displaystyle w}$ $w$ care este furnizat mașinii Turing care acceptă $S.$ ${\ displaystyle S}$ $S.$ nu aparține limbii din urmă, atunci vor exista doar calcule infinite și mașina Turing evident diferă.

Are asta $P\subseteq N\!P$ ${\ displaystyle P \ subseteq N \! P}$ ${\ displaystyle P \ subseteq N \! P}$ . Din această afirmație este clar în primul rând că toate problemele clasei P sunt, de asemenea, probleme ale clasei NP.

Următorul arată că clasa $N\!P$ ${\ displaystyle N \! P}$ ${\ displaystyle N \! P}$ poate fi caracterizat ca acea clasă de probleme pentru care se poate verifica rapid dacă o posibilă soluție este într-adevăr așa.

Teorema proiecției

Este $S\subseteq A^{*}$ ${\ displaystyle S \ subseteq A ^ {*}}$ ${\ displaystyle S \ subseteq A ^ {*}}$ o limbă sau o problemă. Atunci vom avea asta $S\in N\!P$ ${\ displaystyle S \ in N \! P}$ ${\ displaystyle S \ in N \! P}$ dacă și numai dacă există o problemă $T.$ ${\ displaystyle T}$ $T.$ elegant $P.$ ${\ displaystyle P}$ $P.$ ( $T\in P$ ${\ displaystyle T \ în P}$ ${\ displaystyle T \ în P}$ ) și un polinom $p_{s}$ ${\ displaystyle p_ {s}}$ $p_ {s}$ astfel încât problema noastră $S.$ ${\ displaystyle S}$ $S.$ poate fi exprimat ca:

$S=$ ${\ displaystyle S =}$ ${\ displaystyle S =}$ { $w\in A^{*}$ ${\ displaystyle w \ în A ^ {*}}$ ${\ displaystyle w \ în A ^ {*}}$ , $\exists y\in A^{*}$ ${\ displaystyle \ există y \ în A ^ {*}}$ ${\ displaystyle \ există y \ în A ^ {*}}$ cu $|y|\leq p_{s}(|w|)$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ astfel încât $w\sharp y\in$ ${\ displaystyle w \ sharp y \ in}$ ${\ displaystyle w \ sharp y \ in}$ T}

Practic teorema ne face să înțelegem că problema $S.$ ${\ displaystyle S}$ $S.$ este în clasă $N\!P$ ${\ displaystyle N \! P}$ ${\ displaystyle N \! P}$ dacă există o problemă $T.$ ${\ displaystyle T}$ $T.$ a clasei $P.$ ${\ displaystyle P}$ $P.$ (problemă acceptată de o mașinărie Turing deterministă, pe care o numim $M_{t}$ ${\ displaystyle M_ {t}}$ $M_ {t}$ , într-un timp polinomial) astfel încât pentru fiecare $w,y\in A^{*}$ ${\ displaystyle w, y \ în A ^ {*}}$ ${\ displaystyle w, y \ în A ^ {*}}$ Intrarea $w\sharp y$ ${\ displaystyle w \ sharp y}$ ${\ displaystyle w \ sharp y}$ este acceptat de $M_{t}$ ${\ displaystyle M_ {t}}$ $M_ {t}$ în timp polinomial, cu constrângerea că lungimea lui $y$ ${\ displaystyle y}$ $y$ este delimitat polinomial de $w$ ${\ displaystyle w}$ ${\ displaystyle w}$ .

Această din urmă condiție privind lungimea $y$ ${\ displaystyle y}$ $y$ este fundamental să ne asigurăm că verificarea dacă este o soluție eficientă are loc în timp polinomial.

De fapt nu este suficient ca. $T\in P$ ${\ displaystyle T \ în P}$ ${\ displaystyle T \ în P}$ și că, prin urmare $M_{t}$ ${\ displaystyle M_ {t}}$ $M_ {t}$ acceptați $T.$ ${\ displaystyle T}$ $T.$ în timp polinomial. Deci, în esență, putem spune asta $S\in N\!P$ ${\ displaystyle S \ in N \! P}$ ${\ displaystyle S \ in N \! P}$ dacă și numai dacă pentru fiecare $w\in S$ ${\ displaystyle w \ in S}$ $w \ in S$ Sunt capabil să îi asociez o posibilă soluție $y$ ${\ displaystyle y}$ $y$ pe care o pot verifica în timp polinomial.

Demonstrație

Se versetul teoremei) Să presupunem că avem un limbaj $T.$ ${\ displaystyle T}$ $T.$ a clasei $P.$ ${\ displaystyle P}$ $P.$ care este decisă de mașina determinantă de Turing $M_{t}$ ${\ displaystyle M_ {t}}$ $M_ {t}$ și, în plus, să presupunem că condiția este adevărată $|y|\leq p_{s}(|w|)$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ văzută în teoremă. Atunci va trebui să construim mașina Turing nedeterministă $M.$ ${\ displaystyle M}$ $M.$ (cine acceptă $S.$ ${\ displaystyle S}$ $S.$ ) astfel încât pentru fiecare intrare $w$ ${\ displaystyle w}$ $w$ parcurgeți următorii 3 pași:

calculati $p_{s}(|w|)$ ${\ displaystyle p_ {s} (| w |)}$ ${\ displaystyle p_ {s} (| w |)}$
Scrie nedeterministic (adică generează toate configurațiile) $w\sharp y$ ${\ displaystyle w \ sharp y}$ ${\ displaystyle w \ sharp y}$ cu $|y|\leq p_{s}(|w|)$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$
Calculați mașina $M_{t}$ ${\ displaystyle M_ {t}}$ $M_ {t}$ pentru intrare $w\sharp y$ ${\ displaystyle w \ sharp y}$ ${\ displaystyle w \ sharp y}$

Prima observație care se poate face este că mașina nu este deterministă $M.$ ${\ displaystyle M}$ $M.$ are complexitate polinomială, deoarece toți cei trei pași pe care trebuie să-i efectueze sunt astfel. Asa de $C_{M}(n)=O(n^{k})$ ${\ displaystyle C_ {M} (n) = O (n ^ {k})}$ ${\ displaystyle C_ {M} (n) = O (n ^ {k})}$ .

De asemenea, observăm că dacă este adevărat $|y|\leq p_{s}(|w|)$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ și $w\sharp y\in T$ ${\ displaystyle w \ sharp y \ in T}$ ${\ displaystyle w \ sharp y \ in T}$ apoi calculul $M_{t}$ ${\ displaystyle M_ {t}}$ $M_ {t}$ se oprește. Prin urmare, derivăm că dacă $w\sharp y$ ${\ displaystyle w \ sharp y}$ ${\ displaystyle w \ sharp y}$ \în tine $|y|\leq p_{s}(|w|)$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ și $y\in S$ ${\ displaystyle y \ in S}$ ${\ displaystyle y \ in S}$ , $w\in S$ ${\ displaystyle w \ in S}$ $w \ in S$ asa de $M.$ ${\ displaystyle M}$ $M.$ Accept $S.$ ${\ displaystyle S}$ $S.$ . Dar dacă $M.$ ${\ displaystyle M}$ $M.$ (mașina Turing nedeterministă de complexitate polinomială) acceptă $S.$ ${\ displaystyle S}$ $S.$ , înseamnă că $S\in N\!P$ ${\ displaystyle S \ in N \! P}$ ${\ displaystyle S \ in N \! P}$ .

Spre și numai dacă din teoremă) Practic este necesar să se arate că dacă $S\in N\!P$ ${\ displaystyle S \ in N \! P}$ ${\ displaystyle S \ in N \! P}$ , adică dacă $S.$ ${\ displaystyle S}$ $S.$ este acceptat de o mașină nedeterministă de complexitate polinomială, apoi susține că $T\in P$ ${\ displaystyle T \ în P}$ ${\ displaystyle T \ în P}$ , $w\sharp y\in$ ${\ displaystyle w \ sharp y \ in}$ ${\ displaystyle w \ sharp y \ in}$ T și asta $|y|\leq p_{s}(|w|)$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ .

Pentru a face acest lucru, trebuie să construiesc limba $T.$ ${\ displaystyle T}$ $T.$ în mod corespunzător. În acest scop presupunem că $M.$ ${\ displaystyle M}$ $M.$ atât mașina nedeterministă care acceptă $S.$ ${\ displaystyle S}$ $S.$ . După cum știm pentru orice mașină, indiferent dacă este deterministă sau nu, fiecare calcul poate fi reprezentat ca o succesiune de configurații succesive.

În special, pentru fiecare calcul convergent, vom avea că lista configurațiilor succesive este o listă finită. Fiecăreia dintre aceste secvențe de configurații le putem asocia un număr care în cazul nostru va fi binar.

Cu toate acestea, pentru o mașină Turing nedeterministă, deoarece posibilele calcule diferite pe care le realizez pot fi infinite, vor exista probleme. Pentru a remedia acest lucru, putem lua în considerare cuplurile:

$T=$ ${\ displaystyle T =}$ ${\ displaystyle T =}$ { $(w,y)$ ${\ displaystyle (w, y)}$ ${\ displaystyle (w, y)}$ Unde $y$ ${\ displaystyle y}$ $y$ codifică un calcul de $M.$ ${\ displaystyle M}$ $M.$ care se termină pe intrare $w$ ${\ displaystyle w}$ $w$ }

care, după cum putem vedea, dau viață întregului limbaj $T.$ ${\ displaystyle T}$ $T.$ . A acestui limbaj $T.$ ${\ displaystyle T}$ $T.$ trebuie verificată calitatea de membru al clasei de probleme $P.$ ${\ displaystyle P}$ $P.$ . Pentru a face acest lucru, va trebui să verificați acest lucru pentru intrare $w$ ${\ displaystyle w}$ $w$ calculul se oprește cu adevărat.

Practic trebuie verificat că la primul pas vă aflați în stat $q_{0}$ ${\ displaystyle q_ {0}}$ $q_0$ cu intrarea scrisă pe casetă $w$ ${\ displaystyle w}$ $w$ ; atunci este necesar să se verifice dacă fiecare configurație ulterioară derivă din cea anterioară prin intermediul funcției de tranziție $\delta$ ${\ displaystyle \ delta}$ $\ delta$ ; în cele din urmă, trebuie verificat că ultima configurație este o configurație de tip terminal. Dacă toate acestea sunt adevărate atunci $T\in P$ ${\ displaystyle T \ în P}$ ${\ displaystyle T \ în P}$ .

În acest moment trebuie arătat că există un polinom $p_{s}$ ${\ displaystyle p_ {s}}$ $p_ {s}$ astfel încât $|y|\leq p_{s}(|w|)$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ ${\ displaystyle | y | \ leq p_ {s} (| w |)}$ . În acest scop observăm că dacă calculul pe $w$ ${\ displaystyle w}$ $w$ din $M.$ ${\ displaystyle M}$ $M.$ atunci acest calcul converge are un număr polinomial de pași și la fiecare pas am o configurație care are lungime polinomială față de lungimea $w$ ${\ displaystyle w}$ $w$ ; În plus, de asemenea $y$ ${\ displaystyle y}$ $y$ va avea lungime polinomială față de $w$ ${\ displaystyle w}$ $w$ . Deci vom avea polinomul necesar.

Elemente conexe

Portal IT

Portalul de matematică