PSPACE-completo
In teoria della complessità computazionale, un problema decisionale è detto PSPACE-completo quando gli algoritmi che lo risolvono richiedono al massimo una quantità di memoria polinomiale rispetto alla dimensione dell'input. Si chiama PSPACE-completo la 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.[1]
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
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
