PSPACE: differenze tra le versioni

Versione delle 17:56, 9 mar 2013

Versione attuale delle 10:42, 3 apr 2025

(12 versioni intermedie di 11 utenti non mostrate)

Riga 1:

{{SF|matematica|arg2=teorie dell'informazione e dellainformatica|dicembre comunicazione2014}}

Nella [[teoria della complessità algoritmicacomputazionale]], la classe di problemi '''PSPACE''', (dache sta per ''polynomial space''), è l'insieme di tutti i problemi che possono essere risolti da una [[macchina di Turing|macchina di Turing deterministica]] deterministica usando una quantità di memoria di <math>O(n^k)</math>, dove <math>n</math> è la dimensione dei dati di [[input|ingresso]] e <math>k</math> è 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 (matematica)|funzione]] [[polinomio|polinomiale]] della dimensione dell'input.

Riga 6:

== 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 <math>O(n^k)</math>. 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 (complessità)|P]] è inclusa in PSPACE. Infatti, è evidente che se un algoritmo ha un tempo di esecuzione <math>t</math>, potrà utilizzare al più <math>t</math> celle di memoria; se quindi sappiamo che <math>t=O(n^k)</math> per un qualche <math>k</math>, 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 (complessità)|NP]] <math> \subset</math> PSPACE. L'inclusione opposta invece non è dimostrata, e anzi è opinione comune che sia falsa, ovvero che PSPACE<math>\not \subset</math>NP. Questo implicherebbe quindi PSPACE<math>\not \subset</math>P.

Ad accreditare in particolare questa ultima congettura si aggiunge l'esistenza di problemi [[NP-Completo|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 <math>n</math> città, è sufficiente ''contare'' in base <math>n</math> i percorsi possibili, che saranno quelli associati ai numeri di <math>n</math> cifre tutte distinte (questo conteggio richiede una quantità di memoria [[linearità (matematica)|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 <math> \subset </math> P, sarebbe anche vero NPCNP-C <math> \subset </math> P, e quindi NP <math> \subset </math> P (ossia esisterebberotutti i problemi decidibili in tempo polinomiale rispetto alla dimensione dell'input da una macchina di Turing non deterministica che non sonosarebbero decidibili in tempo polinomiale anche da una macchina di Turing nondeterministicadeterministica). Ciò è impossibile datoDato che le macchine di Turing deterministiche sono un caso particolare di macchine nondeterministiche)non deterministiche ne risulta che P <math> \subset </math> NP, e quindi P = NP. La domanda "P=NP o P <math> \neq </math> NP?" è uno dei [[Problemi per il millennio|problemi del millennio]], ad oggi non risolto, anche se molti esperti credono che P <math> \neq </math> NP.

{{Classi di complessità}}

{{Portale|matematica}}

{{Portale|informatica|matematica}}

[[Categoria:ComplessitàClassi computazionaledi complessità]]

[[Categoria:Matematica per l'informatica]]