|
In [[teoria della complessità computazionale]], un problema decisionale è detto '''PSPACE-completo''' quando gli [[Algoritmo|algoritmi]] che lo risolvono richiedono al massimominimo una quantità di [[Memoria (informatica)|memoria]] [[Polinomio|polinomiale]] rispetto alla dimensione dell'[[input]]. PSPACE-completoe corrispondequando alla [[classe di complessità]] computazionale che rappresentatutti i problemi decisionalirisolti checon sonomemoria almenopolinomiale altrettantopossono difficiliessere dei[[Riduzione problemi(informatica)|ridotti]] piùad difficiliesso in [[PSPACE]]tempo polinomiale.
PSPACE-completo corrisponde alla [[classe di complessità]] computazionale che rappresenta i problemi decisionali che sono almeno altrettanto difficili dei problemi più difficili in [[PSPACE]].
Un problema è quindi definito PSPACE-completo se appartiene a PSPACE e se ogni problema in PSPACE si riduce ad esso in tempo polinomiale. Questo significa che risolvere un problema PSPACE-completo richiede almeno tanto spazio quanto risolvere qualsiasi altro problema in PSPACE, e la sua difficoltà computazionale è tale da poter essere utilizzato per risolvere qualsiasi altro problema in PSPACE attraverso una trasformazione in tempo polinomiale.<ref>Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). ''Introduction to Automata Theory, Languages, and Computation'' (3rd ed.). Addison-Wesley.</ref> ▼
La classe PSPACE-completo è una sottoclasse della classe PSPACE, che rappresenta tutti i problemi decisionali che possono essere risolti da una [[macchina di Turing]] deterministica che utilizza una quantità di spazio polinomiale rispetto alla dimensione dell'input. La definizione di PSPACE-completo è stata introdotta da [[Stephen Cook]] nel 1971, e da allora ha avuto un ruolo fondamentale nella teoria della complessità computazionale, in particolare nell'ambito della dimostrazione di limiti inferiori per la complessità dei problemi computazionali.
==Definizione==
# ''A'' appartiene a PSPACE, cioè può essere risolto utilizzando una quantità di memoria polinomiale rispetto alla dimensione dell'input.
# Ogni problema ''B'' in PSPACE può essere ridotto ad ''A'' tramite una [[Riduzione (informatica)|riduzione]] in tempo polinomiale. Questo significa che esiste una funzione computabile ''f'', che può essere calcolata in tempo polinomiale, tale che per ogni input ''x'', ''B(x)'' è vero se e solo se ''A(f(x))'' è vero.<ref>Papadimitriou, C. H. (1994). ''Computational Complexity''. Addison-Wesley</ref>
▲Un problema è quindi definito PSPACE-completo se appartiene a PSPACE e se ogni problema in PSPACE si riduce ad esso in tempo polinomiale. Questo significa che risolvere un problema PSPACE-completo richiede almeno tantotanta spaziomemoria quanto risolvere qualsiasi altro problema in PSPACE, e la sua difficoltà computazionale è tale da poter essere utilizzato per risolvere qualsiasi altro problema in PSPACE attraverso una trasformazione in tempo polinomiale .<ref>Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). ''Introduction to Automata Theory, Languages, and Computation'' (3rd ed.). Addison-Wesley.</ref> .
== Proprietà==
La classe di problemi PSPACE-completicompleto è ununa sottoinsiemesottoclasse della classe PSPACE, che comprenderappresenta tutti i problemi risolvibilidecisionali inche possono essere risolti da una [[macchina di Turing]] deterministica che utilizza una quantità di spazio polinomiale rispetto alla dimensione dell'input. ComprendeI ancheproblemi PSPACE-completi comprendono alcuni dei problemi più difficili in PSPACE. SeLa undefinizione problemadi PSPACE-completo puòè esserestata risoltointrodotta in tempo polinomiale, allorada [[PStephen (complessità)|PCook]] = PSPACE.nel Tuttavia1971, la relazione tra P e PSPACEda rimaneallora apertaha eavuto nonun siruolo safondamentale senella Pteoria =della PSPACE.<ref>Fortnowcomplessità computazionale, L.in (2009).particolare nell''Theambito Statusdella ofdimostrazione thedi Plimiti Versusinferiori NPper Problem''.la Communicationscomplessità ofdei theproblemi ACM, 52(9), 78-86computazionali.</ref>
Se un problema PSPACE-completo può essere risolto in tempo polinomiale, allora [[P (complessità)|P]] = PSPACE. Tuttavia, la relazione tra P e PSPACE rimane aperta e non si sa se P = PSPACE.<ref>Fortnow, L. (2009). ''The Status of the P Versus NP Problem''. Communications of the ACM, 52(9), 78-86.</ref>
== Esempi di problemi PSPACE-completi ==
| 