On the maximum satisfiability of random formulas

Dimitris Achlioptas; Assaf Naor; Yuval Peres

doi:10.1145/1219092.1219098

On the maximum satisfiability of random formulas

Dimitris Achlioptas, Assaf Naor, Yuval Peres

Research output: Contribution to journal › Article › peer-review

22 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 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	https://doi.org/10.1145/1219092.1219098
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

Access to Document

10.1145/1219092.1219098

Cite this

@article{0b17e70f4e3e456b86306fc87badbd77,

title = "On the maximum satisfiability of random formulas",

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.",

keywords = "Maximum satisfiability",

author = "Dimitris Achlioptas and Assaf Naor and Yuval Peres",

year = "2007",

month = apr,

day = "1",

doi = "10.1145/1219092.1219098",

language = "English (US)",

volume = "54",

journal = "Journal of the ACM",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

T1 - On the maximum satisfiability of random formulas

AU - Achlioptas, Dimitris

AU - Naor, Assaf

AU - Peres, Yuval

PY - 2007/4/1

Y1 - 2007/4/1

N2 - 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.

AB - 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.

KW - Maximum satisfiability

UR - http://www.scopus.com/inward/record.url?scp=34247252979&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34247252979&partnerID=8YFLogxK

U2 - 10.1145/1219092.1219098

DO - 10.1145/1219092.1219098

M3 - Article

AN - SCOPUS:34247252979

SN - 0004-5411

VL - 54

JO - Journal of the ACM

JF - Journal of the ACM

IS - 2

M1 - 1219098

ER -

On the maximum satisfiability of random formulas

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this