PSPACE-completo: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
mancava la parte di "completezza" nell'incipit |
+W, corsivi |
||
Riga 1:
{{W|informatica|maggio 2023|mancano i template di citazione, con una nota inserita semplicemente come url, e le formule matematiche (al momento la notazione è inserita con il corsivo)}}
In [[teoria della complessità computazionale]], un problema decisionale è detto '''PSPACE-completo''' quando gli [[Algoritmo|algoritmi]] che lo risolvono richiedono al minimo una quantità di [[Memoria (informatica)|memoria]] [[Polinomio|polinomiale]] rispetto alla dimensione dell'[[input]] e quando tutti i problemi risolti con memoria polinomiale possono essere [[Riduzione (informatica)|ridotti]] ad esso in tempo polinomiale.
Line 25 ⟶ 26:
===Il gioco di Hex===
''[[Hex (gioco)|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.<ref>Reisch, S. (1981). ''Hex ist PSPACE-vollständig''. Acta Informatica, 15(2), 167-191.</ref>
=== Il problema delle mosse valide nel gioco di Reversi ===
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>
==Note ==
<references />
| |||