PSPACE-completo
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. In altre parole, 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
