Accession Number:

ADA461999

Title:

Satometer: How Much Have We Searched? (Preprint)

Descriptive Note:

Conference paper

Corporate Author:

MICHIGAN UNIV ANN ARBOR DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

Report Date:

2002-06-01

Pagination or Media Count:

18.0

Abstract:

We introduce Satometer, a tool that can be used to estimate the percentage of the search space actually explored by a backtrack SAT solver. Satometer calculates a normalized minterm count for those portions of the search space identified by conflicts. The computation is carried out using a zero-suppressed binary decision diagram ZBDD data structure and can have adjustable accuracy. The data provided by Satometer can help diagnose the performance of SAT solvers and can shed light on the nature of a SAT instance.

Subject Categories:

  • Numerical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE