PSPACE: differenze tra le versioni

Versione delle 13:31, 13 mar 2018

Versione attuale delle 10:42, 3 apr 2025

(4 versioni intermedie di 4 utenti non mostrate)

Riga 1:

{{F|matematica|arg2=teorie dell'informatica|dicembre 2014}}

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.

Line 14 ⟶ 15:

{{Classi di complessità}}

{{Portale|Informaticainformatica|Matematicamatematica}}

[[Categoria:Classi di complessità]]