论文标题
关于$ K $ -CNF公式的满意概率
On the Satisfaction Probabilities of $k$-CNF Formulas
论文作者
论文摘要
满意度的概率PR [$ ϕ $]：= pr $ _ {β：vars（ϕ）\ to \ {0,1 \}} [β\型号]的命题公式$ ϕ $的$ ϕ $是随机分配$β$的可能性。我们研究问题的复杂性$ k $ sat-pr $ _ {> p} $ = {$ ϕ $是$ k $ cnf公式| pr [$ ϕ $]> p}用于固定$ k $和$ p $。虽然3sat-pr $ _ {> 0} $ = 3SAT是NP-Complete，并且Sat-pr $ _ {> 1/2} $是PP-Complete，但Akmal和Williams最近表明3Sat-pr $ _ {> 1/2} $在p和4sat-pr $ _ {> 1/2} $ np-complene in p p pp-complete;但是用来证明这些引人注目的结果的方法保持沉默，例如4sat-pr $ _ {> 3/4} $，使$ k $ sat-pr $ _ {> p} $的计算复杂性为大多数$ k $和$ p $打开。在本文中，我们以三分法的形式给出了完整的表征：$ k $ satpr $ _ {> p} $躺在ac $^0 $中，是nl-complete，或者是np-complete。三分法的证据取决于新的订单理论洞察力：每组$ k $ cnf公式都包含一个最大满意度概率的公式。这种欺骗性的简单语句使我们能够（1）内核化$ k $ sat-pr $ _ {\ ge p} $对于联合参数$ k $和$ p $和$ p $，（2）表明，当trichosy ate in Ac $^0 $或nl $ cn $ cn的trichotomy state in the trichomy state in the trichosy nate in the the n $ cn $ cn $ cn的变量形成后门设置，以及（3） PR [$ ϕ $] <$ P $暗示PR [$ψ$] <$ p $已经适用于$ ϕ $的子集$ψ$仅取决于$ k $和$ p $的$ n $ n $ n $ k $ cnf $ k $ k $ k＆k k y size＆k k＆k k y size＆k y size $ k＆k k＆k k y y的size仅$ k $ k $ k $ k＆k k＆k k y y yeps $ k and y yeps $ k＆quars的大小仅为$ k $ k＆k k＆k k $ k
The satisfaction probability Pr[$ϕ$] := Pr$_{β:vars(ϕ) \to \{0,1\}}[β\models ϕ]$ of a propositional formula $ϕ$ is the likelihood that a random assignment $β$ makes the formula true. We study the complexity of the problem $k$SAT-Pr$_{>p}$ = {$ϕ$ is a $k$CNF formula | Pr[$ϕ$] > p} for fixed $k$ and $p$. While 3SAT-Pr$_{>0}$ = 3SAT is NP-complete and SAT-Pr$_{>1/2}$ is PP-complete, Akmal and Williams recently showed that 3SAT-Pr$_{>1/2}$ lies in P and 4SAT-Pr$_{>1/2}$ is NP-complete; but the methods used to prove these striking results stay silent about, say, 4SAT-Pr$_{>3/4}$, leaving the computational complexity of $k$SAT-Pr$_{>p}$ open for most $k$ and $p$. In the present paper we give a complete characterization in the form of a trichotomy: $k$SAT-Pr$_{>p}$ lies in AC$^0$, is NL-complete, or is NP-complete. The proof of the trichotomy hinges on a new order-theoretic insight: Every set of $k$CNF formulas contains a formula of maximum satisfaction probability. This deceptively simple statement allows us to (1) kernelize $k$SAT-Pr$_{\ge p}$ for the joint parameters $k$ and $p$, (2) show that the variables of the kernel form a backdoor set when the trichotomy states membership in AC$^0$ or NL, and (3) prove locality properties for $k$CNF formulas $ϕ$, by which Pr[$ϕ$] < $p$ implies that Pr[$ψ$] < $p$ holds already for a subset $ψ$ of $ϕ$'s clauses whose size depends only on $k$ and $p$, and Pr[$ϕ$] = $p$ implies $ϕ\equiv ψ$ for some $k$CNF formula $ψ$ whose size once more depends only on $k$ and $p$.
