### Abstract

Maximum satisfiability is a canonical NP-complete problem that appears empirically hard for random instances. At the same time, it is rapidly becoming a canonical problem for statistical physics. In both of these realms, evaluating new ideas relies crucially on knowing the maximum number of clauses one can typically satisfy in a random k-CNF formula. In this paper we give asymptotically tight estimates for this quantity. Our result gives very tight bounds for the fraction of satisfiable clauses in a random k-CNF. In particular, for k > 2 it improves upon all previously known such bound.

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

Title of host publication | Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 |

Publisher | IEEE Computer Society |

Pages | 362-370 |

Number of pages | 9 |

ISBN (Electronic) | 0769520405 |

DOIs | |

State | Published - 2003 |

Event | 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 - Cambridge, United States Duration: Oct 11 2003 → Oct 14 2003 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2003-January |

ISSN (Print) | 0272-5428 |

### Other

Other | 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 |
---|---|

Country | United States |

City | Cambridge |

Period | 10/11/03 → 10/14/03 |

### Keywords

- Benchmark testing
- Computer science
- Glass
- H infinity control
- Mathematics
- NP-complete problem
- Operations research
- Physics
- Stationary state
- Statistics

### ASJC Scopus subject areas

- Computer Science(all)

## Fingerprint Dive into the research topics of 'On the maximum satisfiability of random formulas'. Together they form a unique fingerprint.

## Cite this

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

*Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003*(pp. 362-370). [1238210] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2003-January). IEEE Computer Society. https://doi.org/10.1109/SFCS.2003.1238210