## Abstract

On input a random 3-CNF formula of clauses-to-variables ratio r_{3} applies repeatedly the following simple heuristic: Set to TRUE a literal that appears in the maximum number of clauses, irrespective of their size and the number of occurrences of the negation of the literal (ties are broken randomly; 1-clauses when they appear get priority). We prove that for r_{3} < 3.42 this heuristic succeeds with probability asymptotically bounded away from zero. Previously, heuristics of increasing sophistication were shown to succeed for r_{3} < 3.26. We improve up to r_{3} < 3.52 by further exploitingthe degree of the negation of the evaluated to TRUE literal.

Original language | English (US) |
---|---|

Pages (from-to) | 444-480 |

Number of pages | 37 |

Journal | Random Structures and Algorithms |

Volume | 28 |

Issue number | 4 |

DOIs | |

State | Published - Jul 2006 |

## ASJC Scopus subject areas

- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics