Friends-and-strangers is PSPACE-complete.

Chao Yang Zhujun Zhang

Published in: CoRR (2024)

Keyphrases

pspace complete
np complete
model checking
decision problems
satisfiability problem
exptime complete
strips planning
causal graph
tree automata
temporal logic
phase transition
constraint satisfaction
computational complexity
decision making
special case
finite state
utility function
constraint satisfaction problems