On the maximum satisfiability of random formulas

Dimitris Achlioptas, Assaf Naor, Yuval Peres

Research output: Contribution to journalArticle

16 Scopus citations

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 Fk(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 languageEnglish (US)
Article number1219098
JournalJournal of the ACM
Volume54
Issue number2
DOIs
StatePublished - Apr 1 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • Maximum satisfiability

Cite this