Accession Number : ADA325940

Title :   Toward A Good Algorithm for Determining Unsatisfiability of Propositional Formulas,

Corporate Author : CINCINNATI UNIV OH

Personal Author(s) : Franco, John ; Swaminathan, R.

PDF Url : ADA325940

Report Date : 20 MAY 1997

Pagination or Media Count : 9

Abstract : We present progress toward an algorithm that provides short certificates of unsatisfiability with high probability when inputs are random instances of 3-SAT. Such an algorithm would incorporate an approximation algorithm A for the 3-Hitting Set problem. Using A it would determine an approximation for the minimum fraction of variables that must be set to true (false) in order to satisfy the positive (negative) clauses. If the fraction is high enough, then the instance is deemed unsatisfiable.

Descriptors :   *MATHEMATICAL MODELS, *ALGORITHMS, PROBABILITY DISTRIBUTION FUNCTIONS, RANDOM VARIABLES, APPROXIMATION(MATHEMATICS), HEURISTIC METHODS, SET THEORY.

Subject Categories : Operations Research
      Statistics and Probability

Distribution Statement : APPROVED FOR PUBLIC RELEASE