PPT Slide

GSAT outperforms Davis-Putnam on, e.g.:

• Hard random formulas

  • DP: up to 400 vars; GSAT: 2000+ var formulas.

• Boolean encodings of graph coloring problems.

  • GSAT competitive with direct encodings.

• Encodings of Boolean circuit synthesis and diagnosis problems.

Previous slide

Next slide

Back to first slide

View graphic version