PSPACE-Hardness of some combinatorial games (Q1090274): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3944542 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4099541 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Combinatorial Problem Which Is Complete in Polynomial Space / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of problems in games, graphs and algebraic equations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Theory of annihilation games. I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: GO Is Polynomial-Space Hard / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the complexity of some two-person perfect-information games / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4131648 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A complete analysis of von Neumann's Hackendot / rank | |||
Normal rank |
Latest revision as of 20:04, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | PSPACE-Hardness of some combinatorial games |
scientific article |
Statements
PSPACE-Hardness of some combinatorial games (English)
0 references
1987
0 references
PSPACE-hardness of four families of win-lose-draw games played on a digraph with blocking, capture, or annihilation rules is proved. Special cases of three of the families are shown to be PSPACE-complete. Further, the PSPACE-completeness of six families of win-lose games in which two players mark or remove nodes of digraphs according to given rules is proved. The first two families contain partizan games, the last eight impartial games. All the games have been defined previously in the literature or are slight variations of such games.
0 references
games on digraphs
0 references
combinatorial games
0 references
PSPACE-hardness
0 references
blocking, capture
0 references
annihilation
0 references
PSPACE-completeness
0 references
partizan games
0 references
impartial games
0 references