PSPACE-completo: differenze tra le versioni

Versione delle 20:20, 9 mag 2023

Versione delle 20:29, 9 mag 2023

Riga 4:

Il concetto di '''PSPACE-completo''' è centrale nell'ambito della [[teoria della complessità computazionale]], che studia la quantità di risorse (tempo e spazio) necessarie per risolvere un problema attraverso un algoritmo. In particolare, PSPACE-completo è la [[classe di complessità]] computazionale che rappresenta i problemi decisionali che richiedono una quantità di memoria polinomiale rispetto alla dimensione dell'input, e che sono almeno altrettanto difficili, dal punto di vista della complessità computazionale, dei problemi più difficili in [[PSPACE]].

Un problema è definito PSPACE-completo se appartiene a PSPACE e se ogni problema in PSPACE si riduce ad esso in tempo polinomiale. InQuesto altresignifica parole,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.