PSPACE

Nella teoria della complessità computazionale, la classe di problemi PSPACE, che sta per 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 input 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, cioè la classe di problemi che possono essere risolti da una macchina di Turing non deterministica usando una quantità di memoria di $O(n^{k})$. Ciò significa che le due classi sono equivalenti in termini di potenza computazionale. Inoltre si osserva facilmente che la ben più conosciuta classe di complessità P è inclusa in PSPACE. Infatti, è evidente che se un algoritmo ha un 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.