PSPACE-completo
Il PSPACE-completo è una classe di complessità computazionale che rappresenta i problemi decisionali che richiedono al massimo 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. Questa classe è una sottoclasse della classe PSPACE.[1]
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.[2]
Proprietà
La classe di problemi PSPACE-completi è un sottoinsieme della classe PSPACE, che comprende problemi risolvibili in spazio polinomiale. Comprende anche alcuni dei problemi più difficili in PSPACE. 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
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.[4]
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.[5]
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.[6]
Sokoban
Il gioco Sokoban, in cui un omino deve spostare casse verso una posizione indicata, è PSPACE-completo.[7]
Note
- ^ Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley.
- ^ Papadimitriou, C. H. (1994). Computational Complexity. 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