Loading AI tools
classe di complessità Da Wikipedia, l'enciclopedia libera
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.
Un problema decisionale A è definito PSPACE-completo se:
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].
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.[3]
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]
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 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]
Il gioco Sokoban, in cui un omino deve spostare casse verso una posizione indicata, è PSPACE-completo.[7]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.