Strings-and-Coins and Nimstring are PSPACE-complete.

Erik D. Demaine Yevhenii Diomidov

Published in: CoRR (2021)

Keyphrases

pspace complete
np complete
model checking
satisfiability problem
decision problems
tree automata
strips planning
temporal logic
finite automata
np hard
computational complexity
causal graph
coalition logic
database
cellular automata
relational databases
search algorithm