On the maximum satisfiability of random formulas

D. Achlioptas, A. Naor, Y. Peres

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

6 Scopus citations

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 - Jan 1 2003
Externally publishedYes
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

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

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

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

Cite this