Bounded-width QBF is PSPACE-complete.
Albert AtseriasSergi OlivaPublished in: Electron. Colloquium Comput. Complex. (2012)
Keyphrases
- pspace complete
- np complete
- model checking
- satisfiability problem
- decision problems
- strips planning
- boolean formula
- quantified boolean formulas
- temporal logic
- causal graph
- np hard
- conjunctive normal form
- tree automata
- computational complexity
- conjunctive queries
- utility function
- orders of magnitude
- optimal policy
- coalition logic