PSPACE

În teoria complexității algoritmice , clasa problemelor PSPACE (din spațiul polinomial ) este ansamblul tuturor problemelor care pot fi rezolvate de o mașinărie Turing deterministă folosind o cantitate de memorie de $O(n^{k})$ ${\ displaystyle O (n ^ {k})}$ ${\ displaystyle O (n ^ {k})}$ , unde este $n$ ${\ displaystyle n}$ $n$ este dimensiunea datelor de intrare e $k$ ${\ displaystyle k}$ $k$ este orice valoare finită.

Cu alte cuvinte, PSPACE include acele probleme care pot fi rezolvate de un algoritm care utilizează un spațiu de memorie a cărui dimensiune este cel mult o funcție polinomială a dimensiunii intrării.

Proprietățile clasei

Conform teoremei lui Savitch , această clasă este echivalentă cu NPSPACE . Mai mult, este ușor de observat că clasa de complexitate P mult mai cunoscută este inclusă în PSPACE. De fapt, este evident că dacă un algoritm are timp de execuție $t$ ${\ displaystyle t}$ $t$ , va putea folosi cel mult $t$ ${\ displaystyle t}$ $t$ celule de memorie; dacă da, știm asta $t=O(n^{k})$ ${\ displaystyle t = O (n ^ {k})}$ ${\ displaystyle t = O (n ^ {k})}$ pentru unii $k$ ${\ displaystyle k}$ $k$ , neapărat spațiul folosit este limitat în același mod.

Același raționament, combinat cu observația făcută înainte de PSPACE = NPSPACE, ne permite să demonstrăm și includerea NP $\subset$ ${\ displaystyle \ subset}$ ${\ displaystyle \ subset}$ PSPACE. Incluziunea opusă, pe de altă parte, nu este dovedită și, într-adevăr, opinia comună este că este falsă, adică PSPACE $\not \subset$ ${\ displaystyle \ not \ subset}$ ${\ displaystyle \ not \ subset}$ NP. Prin urmare, aceasta ar implica PSPACE $\not \subset$ ${\ displaystyle \ not \ subset}$ ${\ displaystyle \ not \ subset}$ P.

În special, existența unor probleme NP complete aparținând clasei PSPACE este adăugată pentru a credita această ultimă conjectură. De exemplu, este posibil să se rezolve problema vânzătorului călător în timp exponențial, dar cu utilizarea memoriei polinomiale: data $n$ ${\ displaystyle n}$ $n$ oraș, pur și simplu numărați în bază $n$ ${\ displaystyle n}$ $n$ căile posibile, care vor fi cele asociate cu numărul de $n$ ${\ displaystyle n}$ $n$ toate cifrele distincte (acest număr necesită o cantitate liniară de memorie în numărul de orașe) și pentru fiecare rută calculați suma distanțelor dintre diferitele orașe (această operație are și un cost liniar în spațiu). Aceasta înseamnă că dacă ar fi adevărat că PSPACE $\subset$ ${\ displaystyle \ subset}$ $\ subset$ P, NP-C ar fi, de asemenea, adevărat $\subset$ ${\ displaystyle \ subset}$ $\ subset$ P și, prin urmare, NP $\subset$ ${\ displaystyle \ subset}$ $\ subset$ P (adică toate problemele care pot fi decise în timp polinomial cu privire la dimensiunea intrării de către o mașină de Turing nedeterministă ar putea fi decise în timp polinomial și de o mașină de Turing deterministă). Deoarece mașinile Turing deterministe sunt un caz particular al mașinilor nedeterministe, rezultă că P $\subset$ ${\ displaystyle \ subset}$ $\ subset$ NP și, prin urmare, P = NP. Întrebarea „P = NP sau P $\neq$ ${\ displaystyle \ neq}$ ${\ displaystyle \ neq}$ NP? "Este una dintre problemele mileniului , până în prezent, nerezolvată, chiar dacă mulți experți cred că P $\neq$ ${\ displaystyle \ neq}$ ${\ displaystyle \ neq}$ NP.

Portal IT

Portalul de matematică