Accession Number:

ADA179537

Title:

Probabilistic Analysis of Algorithms for NP-Complete Problems.

Descriptive Note:

Annual rept. Oct 85-Sep 86,

Corporate Author:

INDIANA UNIV AT BLOOMINGTON DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1986-10-01

Pagination or Media Count:

24.0

Abstract:

The probabilistic performance of a number of algorithms for the NP-complete satisfiability Problem SAT has been investigated analytically and experimentally using a fixed-clause-length model generating n clauses of k - 3 literals taken from r variables as well as a random-clause-length model generating n clauses containing each of r variables independently with probability P. In the case of the random instance I of SAT with probability approachingas in and r get large when a solution exists for I. In the case of the fixed-clause-length model, we have discovered an algorithm which almost always finds a solution to random satisfiable instances of SAT with k 3. We have also shown that none of a wide class of algorithms can verify unsatisfiability in polynomial time almost always.

Subject Categories:

Distribution Statement:

APPROVED FOR PUBLIC RELEASE