Bounded-width QBF is PSPACE-complete.

Albert Atserias Sergi Oliva

Published in: STACS (2013)

Keyphrases

pspace complete
np complete
model checking
satisfiability problem
decision problems
strips planning
quantified boolean formulas
tree automata
np hard
conjunctive normal form
coalition logic
boolean formula
temporal logic
causal graph
finite state
pattern matching
phase transition