QSAT phase transition

• Fixed clause length model

  • k alternating quantifiers
  • each with n variables
  • l clauses each with h literals

• Cadoli et al (AI*IA97, AAAI98)

  • not always an easy-hard-easy pattern
  • solubility transition at l µÖn

Previous slide

Next slide

Back to first slide

View graphic version