Image

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 ...

Get The Art of Computer Programming: Satisfiability, Volume 4, Fascicle 6 now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.