Algorithms and Problems for Quantified SAT
Quantified satisfiability (QSAT)
Complexity of QSAT
Algorithms for QSAT
Cadoli et al's Evaluate algorithm
An unusual preprocessing step
Function U-Evaluate(F)
Function E-Evaluate(F)
Thoughts about theAlgorithms
Failure Driven Search
No-commitment Search
Hard and Soft Clauses
Revised E-evaluate
Revised U-evaluate([F])
Comments
Conclusions (Algorithms)
Phase transition behaviour
Other complexity classes
QSAT phase transition
Flawed problem generation!
Conclusions (Transitions)
Email: ipg@dcs.st-and.ac.uk
Home Page: http://www.dcs.st-and.ac.uk/~ipg