PSPACE

Nella teoria della complessità algoritmica, la classe di problemi PSPACE (da polynomial space) è l'insieme di tutti i problemi che possono essere risolti da una macchina di Turing deterministica usando una quantità di memoria di $O(n^{k})$, dove $n$ è la dimensione dei dati di ingresso e $k$ è un qualsiasi valore finito.

In altre parole, PSPACE include quei problemi che possono essere risolti da un algoritmo che utilizzi uno spazio di memoria la cui dimensione sia al più funzione polinomiale della dimensione dell'input.

Proprietà della classe

Per il teorema di Savitch, questa classe risulta equivalente a NPSPACE. Inoltre si osserva facilmente che la ben più conosciuta classe di complessità P è inclusa in PSPACE. Infatti è evidente che se un algoritmo ha tempo di esecuzione $t$, potrà utilizzare al più $t$ celle di memoria; se quindi sappiamo che $t=O(n^{k})$ per un qualche $k$, necessariamente lo spazio utilizzato è limitato allo stesso modo.

Questo stesso ragionamento, unito all'osservazione fatta prima che PSPACE = NPSPACE, ci permette di dimostrare anche l'inclusione NP $\subset$ PSPACE. L'inclusione opposta invece non è dimostrata, e anzi è opinione comune che sia falsa, ovvero che PSPACE$\not \subset$NP. Questo implicherebbe quindi PSPACE$\not \subset$P.

Ad accreditare in particolare questa ultima congettura si aggiunge l'esistenza di problemi NP completi appartenenti alla classe PSPACE. Ad esempio, è possibile risolvere in tempo esponenziale ma con utilizzo di memoria polinomiale il problema del commesso viaggiatore: date $n$ città, è sufficiente contare in base $n$ i percorsi possibili, che saranno quelli associati ai numeri di $n$ cifre tutte distinte (questo conteggio richiede una quantità di memoria lineare nel numero di città) e per ogni percorso calcolare la somma delle distanze tra le varie città (anche questa operazione ha costo lineare in spazio). Questo significa che se fosse vero che PSPACE $\subset$ P, sarebbe anche vero NP-C $\subset$ P, e quindi NP $\subset$ P (ossia tutti i problemi decidibili in tempo polinomiale rispetto alla dimensione dell'input da una macchina di Turing non deterministica sarebbero decidibili in tempo polinomiale anche da una macchina di Turing deterministica). Dato che le macchine di Turing deterministiche sono un caso particolare di macchine non deterministiche ne risulta che P $\subset$ NP, e quindi P = NP. La domanda "P=NP o P $\neq$ NP?" è uno dei problemi del millennio, ad oggi non risolto, anche se molti esperti credono che P $\neq$ NP.