Complexity of QSAT

• PSPACE-complete

  • no limit on number of alternating quantifiers
  • problems needing polynomial space on a Turing machine

• k-QSAT

  • k alternations, $ innermost
  • Sk P-complete

• CNF formulae

  • does not change complexity

Previous slide

Next slide

Back to first slide

View graphic version