Generating Hard Random Formulas

• Key: Use fixed-clause-length model.

  (Mitchell, Selman, and Levesque 1992)
  

• Critical parameter: ratio of the number of clauses to the number of variables.

• Hardest 3SAT problems at ratio = 4.3

Previous slide

Next slide

Back to first slide

View graphic version