Access Restriction

Author Achlioptas, Dimitris ♦ Naor, Assaf ♦ Peres, Yuval
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2007
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Maximum satisfiability
Abstract Say that a $\textit{k}-CNF$ a formula is $\textit{p-satisfiable}$ if there exists a truth assignment satisfying a fraction 1 ™ $2^{™k}$ $+\textit{p}$ $2^{™k}$ of its clauses (note that every $\textit{k}-CNF$ formula is 0-satisfiable). Let $F_{k}(n,$ $\textit{m})$ denote a random $\textit{k}-CNF$ formula on $\textit{n}$ variables with $\textit{m}$ clauses. For every $\textit{k}≥2$ and every $\textit{r}>0$ we determine $\textit{p}$ and $Δ=Δ(k)=O(k2^{™k/2})$ such that with probability tending to 1 as $\textit{n}→∞,$ a random $\textit{k}-CNF$ formula $F_{k}(n,$ $\textit{rn})$ is $\textit{p}-satisfiable$ but not $(\textit{p}+Δ)-satisfiable.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2007-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 54
Issue Number 2

Open content in new tab

   Open content in new tab
Source: ACM Digital Library