Statements (23)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:board_game
theoretical computer science combinatorial game |
| gptkbp:complexity |
PSPACE-complete
|
| gptkbp:field |
gptkb:mathematics
theoretical computer science |
| gptkbp:firstDescribed |
gptkb:David_S._Johnson
gptkb:Michael_R._Garey 1979 |
| gptkbp:goal |
force opponent into a position with no legal moves
|
| gptkbp:hasApplication |
gptkb:complexity_theory
|
| gptkbp:hasVariant |
gptkb:Undirected_Geography
gptkb:Vertex_Geography Edge Geography |
| https://www.w3.org/2000/01/rdf-schema#label |
Generalized Geography
|
| gptkbp:movement |
alternating moves
removal of vertices |
| gptkbp:notableFor |
early example of PSPACE-complete problem
|
| gptkbp:numberOfPlayers |
two
|
| gptkbp:played_for |
graph
|
| gptkbp:relatedTo |
gptkb:Geography_(word_game)
|
| gptkbp:bfsParent |
gptkb:PSPACE
|
| gptkbp:bfsLayer |
5
|