Other complexity classes

• Polynomial problems

  • enforcing arc-consistency in CSPs [CP-97]
  • worst-case complexity seen at phase boundary
  • k useful to predict location of transition

• What about higher complexity classes?

Previous slide

Next slide

Back to first slide

View graphic version