Satometer: How Much Have We Searched? (Preprint)

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 2002
Accession Number
ADA461999

Entities

People

  • Brian D. Sierawski
  • Fadi A. Aloul
  • Karem A. Sakallah

Organizations

  • University of Michigan

Tags

Communities of Interest

  • C4I
  • Human Systems

DTIC Thesaurus Topics

  • Abstracts
  • Accuracy
  • Algorithms
  • Boolean Algebra
  • Computations
  • Computer Science
  • Computers
  • Databases
  • Electrical Engineering
  • Engineering
  • Errors
  • Estimators
  • Lists (Data Structures)
  • Operating Systems
  • Standards
  • Symmetry
  • Terminals

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computational Modeling and Simulation
  • Computer Engineering

Technology Areas

  • Space