The Art of Computer Programming: Satisfiability, Volume 4, Fascicle 6

Fig. 53. Comparison of Algorithms C and L on 100 moderately difficult satisfiability problems.

All of these experiments were aborted after 50 Gμ, if necessary, since many of these problems could potentially take centuries before running to completion. Thus the test cases for which Algorithm L timed out appear at the right edge of Fig. 53, and the tough cases for Algorithm C appear at the top. Only E2 and X8 were too hard for both algorithms to handle within the specified cutoff time.

Algorithm L is deterministic: It uses no random variables. However, a slight change (see exercise 505) will randomize it, because the inputs can be shuffled as ...