- $\text{Ex3SAT}$ : Each clause has exact $3$ variables
- $\text{Pl}$ : The incidence graph of a formula $\Phi$ is planar
- $\text{Tree}$ : The incidence graph of a formula $\Phi$ is a tree
- $\text{Mon}$ : Monotone, i.e., each variable occurs only in positive form
- $\text{Rtw}$ : ReadTwice, i.e., each variable occurs at most twice
- $\text{x-in-N}$ : Exactly $x$ variables out of $N$ must be true in each clause. So $\text{1-in-3-3CNF}$ also forces that each clause has exactly 3 variables and not less. So $\text{1-in-3-Ex3CNF}$ is actually the same.
- $\text{RtwOpp}$ : The variable occurs twice but in opposite value, i.e., once negative and once positive
- $\text{Nae}$ : Not all equal, i.e., in a satisfying assignment, at least one variable in a clause must be false
Here is the (still incomplete) list:
\begin{array}{| r | c | c | c |}
\hline
\large{\text{Type}} & \large{\text{SAT in:}} & \large{\text{#SAT in}} & \large{\text{Source}} \\
\hline
\text{3CNF} & \text{NP-complete} & \text{#P-complete} & \text{folklore} \\
\hline
\text{Pl-3CNF} & \text{NP-complete} & \text{#P-complete} & [1]\\
\hline
\text{Tree-3CNF} & \text{P} & \text{P} & [2,3]\\
\hline
\text{Mon-3CNF} & \text{NP-complete} & \text{#P-complete} & [1]\\
\hline
\#_2 \text{Pl-Mon-3CNF} & \text{NP-complete} & \otimes \text{P-complete} & [1]\\
\hline
\text{Rtw-3CNF} & \text{NP-complete} & \text{#P-complete} & [5]\\
\hline
\text{Pl-RtwOpp-3CNF} & \text{?} & \text{#P-complete} & [5]\\
\hline
\text{Pl-Rtw-3CNF} & \text{?} & \text{?} & \\
\hline
\text{1-in-3-3CNF} & \text{NP-complete} & \text{#P-complete} & [1,9]\\
\hline
\text{2-in-3-3CNF} & \text{NP-complete} & \text{#P-complete} & [1]\\
\hline
\text{1-in-3-Ex3CNF} & \text{NP-complete} & \text{#P-complete} & [1]\\
\hline
\text{Nae-3CNF} & \text{NP-complete} & \text{#P-complete} & [7,9]\\
\hline
\text{Mon-1-in-3-3CNF} & \text{NP-complete} & \text{#P-complete} & [7]\\
\hline
\text{Mon-2-in-3-3CNF} & \text{NP-complete} & \text{#P-complete} & [7]\\
\hline
\text{Pl-Mon-1-in-3-3CNF} & ? & ? & [?]\\
\hline
\text{Pl-Mon-2-in-3-3CNF} & ? & ? & [?]\\
\hline
\text{Pl-Mon-1-in-3-Ex3CNF} & \text{NP-complete} & \text{#P-complete} & [1]\\
\hline
\text{Pl-Mon-2-in-3-Ex3CNF} & \text{NP-complete} & \text{#P-complete} & via [1]\\
\hline
\text{Mon-Nae-3CNF} & \text{NP-complete} & \text{#P-complete} & [7]\\
\hline
\text{Pl-Nae-Ex3CNF} & \text{P} & \text{P} & [6]\\
\hline
\text{Pl-Rtw-Mon-3CNF} & \text{NP-complete} & \text{#P-complete} & [4]\\
\hline
\#_2 \text{Pl-Rtw-Mon-3CNF} & & \otimes \text{P}-\text{complete} & [4]\\
\hline
\#_{2^k-1} \text{Pl-Rtw-Mon-3CNF} & \text{P} & \text{P} & [4]\\ \hline
\hline
\text{2CNF} & \text{P} & \text{#P-complete} & [8]\\
\hline
\text{Pl-2CNF} & \text{P} & \text{#P-complete} & [4]\\
\hline
\text{Mon-2CNF} & \text{P} & \text{#P-complete} & [4]\\
\hline
\text{Rtw-2CNF} & \text{P} & ? & \\
\hline
\text{Pl-Mon-2CNF} & \text{P} & \text{#P-complete} & [4]\\
\hline
\text{Pl-Rtw-2CNF} & \text{P} & \text{P} & [\text{tba}]\\
\hline
\end{array}
If you look at the list, you will probably ask yourself a lot of questions; at least i do.
As is can be seen from the list, it is $$\text{3CNF} \leq^p_1 \text{Pl-3CNF}, \text{3CNF} \leq^p_1 \text{Mon-3CNF},\;\text{and}\;\text{3CNF} \leq^p_1 \text{Rtw-3CNF}$$ So the restrictions planarity, monotone and read-twice are not strong enough to make deciding sat or counting easier. But if the incidence graph of a formula is actually not only planar but also a tree, then those problems become easier. Because trees have no cycles a lot of problems are easier in trees than in general graphs, but it is often not obvious.
Not much is known (or am i wrong?) about $$\text{3CNF} \stackrel{\text{How to reduce?}}{\rightarrow} \text{Pl-Mon-3CNF}\;\text{or}\; \text{3CNF} \stackrel{\text{How to reduce?}}{\rightarrow} \text{Rtw-Mon-3CNF}$$ It seems that the combination of two restrictions seems to be more problematic than handling only one. Perhaps if one tries to achieve one feature and then the other one, the previous restriction is broken. Don't get me wrong, there are results about, e.g., $\text{Rtw-Mon-3CNF}$, but i could not find something about the actual reduction from $\text{3CNF}$ to $\text{Rtw-Mon-3CNF}$. Nor i could find something useable about $\text{Pl-Rtw-3CNF}$ alone, but i guess they are still hard.
A tree-like incidence graph is a restriction that is alone strong enough to allow polynomial counting (actually it is planar $\rightarrow$ tree). But also the combination of several restrictions, that are alone not strong enough to allow polynomial counting, can also lead to a exponential speedup. If we combine planarity, read-twice and monotone, we get a class of CNF formulas whose solution can be counted mod $2^k$ in polynomial time. In contrast, counting their solutions over the integers remains NP-complete. Since computing the number of solutions mod $2^k$ is enough non-trivial information in many cases, it is no wonder that the actual reduction $$\text{3CNF} \stackrel{\text{how?}}{\rightarrow} \text{Pl-Rtw-Mon-3CNF}$$ is unknown.
$\text{Nae-3CNF}$ formulas are also very strange. By Schaefer's Dichotomy Theorem they are known to be also $\text{NP-complete}$. But if each clause in such a formula has exactly $3$ variables and the incidence graph is planar, then Valiant showed how to count the solutions of $\text{Pl-Nae-Ex3CNF}$ in polynomial time. The decision problem of $\text{Pl-Nae-Ex3CNF}$ could be reduced to the 4-color theorem (hence fast), but counting via this path is cumbersome, since counting 4-colorings is $\text{NP-complete}$, cf. [6]. Similar things can be said about $\text{1-in-3}$ or $\text{2-in-3}$ formulas. They are could be classified as $\text{NP-complete}$ using Schaefer's Theorem, but there exists rumors that $\text{Pl-Mon-2-in-3-3CNF}$, i.e, adding the restriction to be planar and monotone, that they can be counted modulo some prime $p$.
Counting the solutions of $\text{2CNF}$ formulas has also weired exceptions. First, what some people often forget, the satisfiability problem for $\text{2CNF}$ is in $\text{P}$ but counting their number solutions is also $\#\text{P-complete}$.
$\text{Mon-2CNF}$ is equivalent to counting the number of vertex covers which remains hard even for planar graphs. I could not find any references for $\text{Rtw-2CNF}$. But there are again rumors that adding planarity to these formulas helps to count their solutions modulo some prime, hence $\#_p \text{Pl-Rtw-2CNF}$ might possible. But, if you think about it shortly, $\text{Rtw-2CNF}$ formulas can be drawn always planar hence, counting $\text{Rtw-2CNF}$ is perhaps easy.
If suggestions for further entries or corrections are welcome :)
[1] Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, Richard Edwin Stearns: The Complexity of Planar Counting Problems. SIAM J. Comput. 27(4): 1142-1167 (1998)
[2] Eldar Fischer, Johann A. Makowsky, Elena V. Ravve: Counting truth assignments of formulas of bounded tree-width or clique-width. Discrete Applied Mathematics 156(4): 511-529 (2008)
[4] Leslie G. Valiant: Accidental Algorithms. FOCS 2006: 509-517
[5] Jin-Yi Cai, Pinyan Lu, Mingji Xia: Holographic reduction, interpolation and hardness. Computational Complexity 21(4): 573-604 (2012)
[6] Leslie G. Valiant: Holographic Algorithms (Extended Abstract), FOCS 2004: 306-315
[7] Schaefer, Thomas J, The Complexity of Satisfiability Problems,STOC 1978, pp. 216–226.
[8] Valiant, Leslie G. (1979), The complexity of enumeration and reliability problems, SIAM Journal on Computing 8 (3): 410–421,
[9] Nadia Craignou, Miki Hermann, On the complexity of some generalized counting problems, Information and Computation, 125, 1-12
No comments:
Post a Comment