PSPACE-completo: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
m Bot: righe vuote in eccesso e modifiche minori |
||
Riga 32:
Il problema decisionale delle mosse valide in ''[[Othello (gioco)|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.<ref>Robson, J. M. (1983). ''The complexity of Go''. In IFIP Congress (pp. 413-417).</ref>
=== Sokoban ===
Il gioco ''[[Sokoban]]'', in cui un omino deve spostare casse verso una posizione indicata, è PSPACE-completo.<ref>https://www.semanticscholar.org/paper/Sokoban-is-PSPACE-complete-Culberson/7a73f74c2943e5aafef364735302a36ee2f17b26</ref>
Riga 42:
* [[NP-completo]]
* [[Classe di complessità]]
{{Classi di complessità}}
| |||