next up previous
Next: 3.2.1 Prespecified Solution Up: 3 The Satisfiability Problem Previous: 3.1 Highly Constrained SAT

3.2 Random SAT Problems 

Theoretically, search algorithms are often evaluated for the worst possible case. However, in practice, search problems are often found to be considerably easier than suggested by these worst case analyses [32]. This observation leads to examining the typical behavior of search algorithms with respect to a specified ensemble of problems, i.e., a class of problems and a probability for each to occur. For instance, the ensemble of random k-SAT is specified by the number of variables n, the size of the clauses k and the number of distinctgif clauses m.

The quantum algorithm presented in this paper is effective for highly constrained soluble k-SAT problems. When there are many constraints, soluble problems are very rare among randomly generated instances. Thus to study the algorithm's behavior we generate random problems with a prespecified solution. That is, a random assignment is selected to be a solution and used to restrict the selection of clauses for the problem. In the remainder of this section we describe two methods for generating such problems, and how they can be related to corresponding 1-SAT problems.

Tad Hogg
Feb. 1999