Nella teoria della complessità computazionale, un problema decisionale è detto PSPACE-completo quando gli algoritmi che lo risolvono richiedono al minimo una quantità di memoria polinomiale rispetto alla dimensione dell'input e quando tutti i problemi risolti con memoria polinomiale possono essere ridotti ad esso in 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.
Definizione
Un problema decisionale A è definito PSPACE-completo se:
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 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.Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley Un problema è quindi 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 tanta memoria 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 polinomialeHopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley..
Proprietà
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. I problemi PSPACE-completi comprendono alcuni dei problemi più difficili in PSPACE. 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.
Se un problema PSPACE-completo può essere risolto in tempo polinomiale, allora P = PSPACE. Tuttavia, la relazione tra P e PSPACE rimane aperta e non si sa se P = PSPACE.Fortnow, L. (2009). The Status of the P Versus NP Problem. Communications of the ACM, 52(9), 78-86.
Esempi di problemi PSPACE-completi
Quantified Boolean Formulas (QBF)
Il problema QBF è un'estensione del problema della soddisfacibilità booleana (SAT). Mentre SAT chiede se esiste un assegnamento di valori di verità per le variabili booleane che rende vera una formula booleana, QBF generalizza questo problema aggiungendo quantificatori universali ed esistenziali alle variabili booleane. Si è dimostrato che QBF è PSPACE-completo.Stockmeyer, L., & Meyer, A. (1973). Word problems requiring exponential time (Technical Report). MIT.
Il gioco di Hex
Hex è un gioco di strategia su una griglia esagonale che è stato dimostrato essere PSPACE-completo. Il problema decisionale associato è determinare se il giocatore che muove per primo ha una strategia vincente.Reisch, S. (1981). Hex ist PSPACE-vollständig. Acta Informatica, 15(2), 167-191.
Il problema delle mosse valide nel gioco di Reversi
Il problema decisionale delle mosse valide in Othello o Reversi, un gioco da tavolo che coinvolge due giocatori che si alternano a posizionare dischi su una griglia, è stato dimostrato essere PSPACE-completo.Robson, J. M. (1983). The complexity of Go. In IFIP Congress (pp. 413-417).
Sokoban Il gioco Sokoban, in cui un omino deve spostare casse verso una posizione indicata, è PSPACE-completo.
Note
Voci correlate
NP-completo Classe di complessità
Categoria:Classi di complessità