Havannah and TwixT are PSPACE-complete.

Edouard Bonnet Florian Jamain Abdallah Saffidine

Published in: Computers and Games (2013)

Keyphrases

pspace complete
np complete
model checking
satisfiability problem
decision problems
exptime complete
strips planning
tree automata
causal graph
np hard
coalition logic
database
finite state
data complexity
phase transition
temporal logic
constraint satisfaction problems
markov chain
search algorithm
database systems