On the Satisfaction Probabilities of $k$-CNF Formulas
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914906593296384 |
|---|---|
| author | Tantau, Till |
| author_facet | Tantau, Till |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_08895 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the Satisfaction Probabilities of $k$-CNF Formulas Tantau, Till Computational Complexity Logic in Computer Science F.1.3; F.4.1; F.2.2 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$. |
| title | On the Satisfaction Probabilities of $k$-CNF Formulas |
| topic | Computational Complexity Logic in Computer Science F.1.3; F.4.1; F.2.2 |
| url | https://arxiv.org/abs/2201.08895 |