Probabilistic Analysis of Algorithms for NP-Complete Problems.

摘要

This is the final scientific report describing results obtained under Air Force Office of Scientific Research grant number AFOSR-84-0372. The main objective was the probabilistic sense, it is easy to find a satisfying truth assignment to an instance of satisfiability but it is hard to verify that an unsatisfiable instance has a solution. A side issue was the analysis of probabilistic models used to obtain the main results. (KR)