Probabilistic Analysis of Algorithms for NP-Complete Problems.

The goal of this research is to develop and analyze algorithms which can, in some practical sense, solve certain NP-complete problems efficiently. By solve we mean determine whether a solution to a given instance of an NP-complete problem exists where, for the problems we have considered, a solution is an assignment of values to a list of variables which cause some predicate to be true. We do not consider actually finding solutions when they exist since doing so adds unnecessary complexity to the statement of the algorithms the algorithms we consider can all be modified to find solutions without significantly altering performance. NP-complete problems are found in Crytology, Operations Research, Artificial Intelligence, Computer System Design and many other areas. There is no known algorithm for any NP-complete problem which runs in time bounded by a polynomial on the length of the input polynomial time in the worst case nor is one likely to be found. We seek algorithms which solve nearly every instance of specific NP-complete problems in polynomial time.