Problem decydowania, czy monotoniczny CNF implikuje monotoniczny DNF

Rozważ następujący problem decyzyjny

Wejście : monotoniczny CNF $\Phi$ i monotonowy DNF$\Psi$ .

Pytanie : Czy $\Phi \to \Psi$ jest tautologią?

Zdecydowanie możesz rozwiązać ten problem w czasie $O(2^n \cdot \mathrm{poly}(l))$ , gdzie $n$ jest liczbą zmiennych w $\Phi \to \Psi$ a $l$ jest długością wejściową. Z drugiej strony ten problem jest kompletny coNP. Ponadto zmniejszenie który ustala CONP-kompletności także pokazuje, że jeśli nie SETH zawiedzie, ma $O(2^{(1/2 - \varepsilon)n} \mathrm{poly}(l))$algorytm czasu dla tego problemu (dotyczy to każdego dodatniego $\varepsilon$ ). Oto ta redukcja. Niech $A$ będzie (nie-monotonicznym) CNF i niech $x$ będzie jego zmienną. Zamień każde dodatnie wystąpienie $x$ na $y$ i każde ujemne wystąpienie $x$ na $z$ . Zrób to samo dla każdej zmiennej. Niech powstały monotoniczny CNF będzie $\Phi$ . Łatwo zauważyć, że $A$ jest satysfakcjonujące, jeśli $\Phi \to yz \lor \ldots$ nie jest tautologią. Ta redukcja wysadza liczbę zmiennych 2 razy, co implikuje $2^{n/2}$ (Na podstawie SETH) dolna granica wspomniana powyżej.

Jest więc różnica między $2^{n/2}$ a $2^n$ time. Moje pytanie brzmi, czy znany jest lepszy algorytm lub lepsza redukcja od SETH?

Tylko dwie uwagi pozornie związane z problemem:

• odwrotny problem, czy monotonowy DNF implikuje monotoniczny CNF, można w prosty sposób rozwiązać w czasie wielomianowym.

• co ciekawe, problem decydowania, czy $\Phi$ i $\Psi$ obliczą tę samą funkcję, można rozwiązać w quasi-wielomianowym czasie dzięki Fredmanowi i Khachiyanowi (O złożoności dualizacji monotonicznych dysjunkcyjnych normalnych form, Journal of Algorithms 21 (1996), nr 3 , ss. 618–628, doi: 10.1006 / jagm.1996.0062 )

Zakładając SETH, problemu nie da się rozwiązać w czasie dla dowolnego ϵ > 0 .$O\bigl(2^{(1-\epsilon)n}\mathrm{poly}(l)\bigr)$$\epsilon>0$

---

Po pierwsze, pokażę, że dotyczy to bardziej ogólnego problemu, w którym i Ψ mogą być dowolnymi formułami monotonicznymi. W tym przypadku występuje wieloczynnikowa redukcja ctt od TAUT do problemu, który zachowuje liczbę zmiennych. Niech T n t ( x 0 , … , x n - 1 ) oznacza funkcję progową T n t ( x 0 , … , x n - 1 ) = $\Phi$$\Psi$$T^n_t(x_0,\dots,x_{n-1})$ Użycie sieci Ajtai-Komlós-Szemerédi komparatorówT N T może być utworzona przez wielomian wielkości monotonicznej wzorze konstruowalne w czasieP°lr(n).

$$T^n_t(x_0,\dots,x_{n-1})=1\iff\bigl|\{i<n:x_i=1\}\bigr|\ge t.$$ $T^n_t$$\mathrm{poly}(n)$

Biorąc pod uwagę wzór boolowski , możemy użyć reguł De Morgana, aby zapisać go w postaci ϕ ′ ( x 0 , … , x n - 1 , ¬ x 0 , … , ¬ x n - 1 ) , gdzie ϕ ′ jest monotoniczny. Następnie ϕ ( x 0 , … , x n $\phi(x_0,\dots,x_{n-1})$

$$\phi'(x_0,\dots,x_{n-1},\neg x_0,\dots,\neg x_{n-1}),$$ $\phi'$ jest tautologią wtedy i tylko wtedy, gdy implikacje monotoniczne T n t ( x 0 , … , x n - 1 ) → ϕ ′ ( x 0 , … , x n - 1 , N 0 , … , N n - 1 ) są ważne dla każdego t ≤ n , gdzie N i = T n - 1 t$\phi(x_0,\dots,x_{n-1})$ $$T^n_t(x_0,\dots,x_{n-1})\to\phi'(x_0,\dots,x_{n-1},N_0,\dots,N_{n-1})$$ $t\le n$ $$N_i=T^{n-1}_t(x_0,\dots,x_{i-1},x_{i+1},\dots,x_{n-1}).$$

$e$$T^n_t$$t$$e'\le e$$t$$e'\models N_i\leftrightarrow\neg x_i$$e'\models\phi$$e'\models\phi'(x_0,\dots,x_{n-1},N_0,\dots,N_{n-1})$$e\models\phi'(x_0,\dots,x_{n-1},N_0,\dots,N_{n-1})$

---

$2^{\delta n}\mathrm{poly}(l)$$k$$k$$k$$2^{\delta n+O(\sqrt{kn\log n})}\mathrm{poly}(l)$$\delta\ge1$

$k$

$$\phi=\bigvee_{i<l}\Bigl(\bigwedge_{j\in A_i}x_j\land\bigwedge_{j\in B_i}\neg x_j\Bigr),$$ $|A_i|+|B_i|\le k$$i$$n$$n'=n/b$$b\approx\sqrt{k^{-1}n\log n}$$\phi$ $$\tag{$*$}\bigwedge_{u<n'}T^b_{t_u}(x_{bu},\dots,x_{b(u+1)-1})\to \bigvee_{i<l}\Bigl(\bigwedge_{j\in A_i}x_j\land\bigwedge_{j\in B_i}N_j\Bigr)$$ $n'$$t_0,\dots,t_{n'-1}\in[0,b]$$j=bu+j'$$0\le j'<b$ $$N_j=T^{b-1}_{t_u}(x_{bu},\dots,x_{bu+j'-1},x_{bu+j'+1},\dots,x_{b(u+1)-1}).$$ We can write $T^b_{t}$ as a monotone CNF of size $O(2^b)$, hence the LHS of $(*)$ is a monotone CNF of size $O(n2^b)$. On the right-hand side, we may write $N_j$ as a monotone DNF of size $O(2^b)$. Thus, using distributivity, each disjunct of the RHS can be written as a monotone DNF of size $O(2^{kb})$, and the whole RHS is a DNF of size $O(l2^{kb})$. It follows that $(*)$ is an instance of our problem of size $O(l2^{O(kb)})$ in $n$ variables. By assumption, we may check its validity in time $O(2^{\delta n+O(kb)}l^{O(1)})$. We repeat this check for all $b^{n'}$ choices of $\vec t$, thus the total time is $$O\bigl((b+1)^{n/b}2^{\delta n+O(kb)}l^{O(1)}\bigr)=O\bigl(2^{\delta n+O(\sqrt{kn\log n})}l^{O(1)}\bigr)$$ as claimed.

---

We get a tighter connection with the (S)ETH by considering the bounded-width version of the problem: for any $k\ge3$, let $k$-MonImp denote the restriction of the problem where $\Phi$ is a $k$-CNF, and $\Psi$ is a $k$-DNF. The (S)ETH concerns the constants

$$\begin{align*} s_k&=\inf\{\delta:k\text-\mathrm{SAT}\in\mathrm{DTIME}(2^{\delta n})\},\\ s_\infty&=\sup\{s_k:k\ge3\}. \end{align*}$$ Likewise, let us define $$\begin{align*} s'_k&=\inf\{\delta:k\text-\mathrm{MonImp}\in\mathrm{DTIME}(2^{\delta n})\},\\ s'_\infty&=\sup\{s'_k:k\ge3\}. \end{align*}$$ Clearly, $$s'_3\le s'_4\le\dots\le s'_\infty\le1$$ as in the SAT case. We also have $$s'_k\le s_k,$$ and the double-variable reduction in the question shows $$s_k\le2s'_k.$$ Now, if we apply the construction above with constant block-size $b$, we obtain $$s_k\le s'_{bk}+\frac{\log(b+1)}b,$$ hence $$s_\infty=s'_\infty.$$ In particular, SETH is equivalent to $s'_\infty=1$, and ETH is equivalent to $s'_k>0$ for all $k\ge3$.