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