On the maximum satisfiability of random formulas

D. Achlioptas, A. Naor, Y. Peres

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003
PublisherIEEE Computer Society
Pages362-370
Number of pages9
ISBN (Electronic)0769520405
DOIs
StatePublished - 2003
Event44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 - Cambridge, United States
Duration: Oct 11 2003Oct 14 2003

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2003-January
ISSN (Print)0272-5428

Other

Other44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003
CountryUnited States
CityCambridge
Period10/11/0310/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