SRC Technical Note 1997-011

Tight Thresholds for the Pure Literal Rule

Michael Mitzenmacher

We consider the threshold for the solvability of random k-SAT formulas using the pure literal rule. We demonstrate how this threshold can be found by using differential equations to determine the appropriate limiting behavior of the pure literal rule.

Back to the SRC Technical Notes main page.

• PostScript compressed with UNIX compress -- 88 Kbytes
  
• PostScript compressed with GNU compress (gzip) -- 80 Kbytes
  
• PostScript compressed with ZIP -- 80 Kbytes
  
• PostScript -- 152 Kbytes
  
• Portable Document Format (PDF) -- 68 Kbytes