PSPACE-completo
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
modificaUn 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.[1]
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 polinomiale[2].
Proprietà
modificaLa 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.[3]
Esempi di problemi PSPACE-completi
modificaQuantified Boolean Formulas (QBF)
modificaIl 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.[4]
Il gioco di Hex
modificaHex è 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.[5]
Il problema delle mosse valide nel gioco di Reversi
modificaIl 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.[6]
Sokoban
modificaIl gioco Sokoban, in cui un omino deve spostare casse verso una posizione indicata, è PSPACE-completo.[7]
Note
modifica- ^ Papadimitriou, C. H. (1994). Computational Complexity. Addison-Wesley
- ^ Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley.
- ^ Fortnow, L. (2009). The Status of the P Versus NP Problem. Communications of the ACM, 52(9), 78-86.
- ^ Stockmeyer, L., & Meyer, A. (1973). Word problems requiring exponential time (Technical Report). MIT.
- ^ Reisch, S. (1981). Hex ist PSPACE-vollständig. Acta Informatica, 15(2), 167-191.
- ^ Robson, J. M. (1983). The complexity of Go. In IFIP Congress (pp. 413-417).
- ^ https://www.semanticscholar.org/paper/Sokoban-is-PSPACE-complete-Culberson/7a73f74c2943e5aafef364735302a36ee2f17b26
