### Abstract

Say that a k-CNF a formula is p-satisfiable if there exists a truth assignment satisfying a fraction 1 - 2^{-k} +p 2^{-k} of its clauses (note that every k-CNF formula is 0-satisfiable). Let F_{k}(n, m) denote a random k-CNF formula on n variables with m clauses. For every k2 and every r>0 we determine p and Δ=Δ(k)=O(k2^{-k/2}) such that with probability tending to 1 as n→, a random k-CNF formula F _{k}(n, rn) is p-satisfiable but not (p+Δ)-satisfiable.

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

Article number | 1219098 |

Journal | Journal of the ACM |

Volume | 54 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1 2007 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence

### Keywords

- Maximum satisfiability

## Cite this

Achlioptas, D., Naor, A., & Peres, Y. (2007). On the maximum satisfiability of random formulas.

*Journal of the ACM*,*54*(2), [1219098]. https://doi.org/10.1145/1219092.1219098