Problem decydowania, czy monotoniczny CNF implikuje monotoniczny DNF

Zakładając SETH, problemu nie da się rozwiązać w czasie dla dowolnego . $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 oznacza funkcję progową $\Phi$ $\Psi$ $T^n_t(x_0,\dots,x_{n-1})$ Użycie sieci Ajtai-Komlós-Szemerédi komparatorów może być utworzona przez wielomian wielkości monotonicznej wzorze konstruowalne w czasie.

T_{t}^{n} (x_{0}, \dots, x_{n - 1}) = 1 ⟺ | {i < n : x_{i} = 1} | \geq t .

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

T_{t}^{n}

$T^n_t$

p o l y (n)

$\mathrm{poly}(n)$

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

ϕ^{'} (x_{0}, \dots, x_{n - 1}, \neg x_{0}, \dots, \neg 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

są ważne dla każdego

, gdzie

ϕ (x_{0}, \dots, x_{n - 1})

$\phi(x_0,\dots,x_{n-1})$

T_{t}^{n} (x_{0}, \dots, x_{n - 1}) \to ϕ^{'} (x_{0}, \dots, x_{n - 1}, N_{0}, \dots, N_{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 \leq n

$t\le n$

N_{i} = T_{t}^{n - 1} (x_{0}, \dots, x_{i - 1}, x_{i + 1}, \dots, x_{n - 1}) .

$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$

ϕ = \underset{i < l}{⋁} (\underset{j \in A_{i}}{⋀} x_{j} \land \underset{j \in B_{i}}{⋀} \neg x_{j}),

$\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} | \leq k

$|A_i|+|B_i|\le k$

i

$i$

n

$n$

n^{'} = n / b

$n'=n/b$

b \approx \sqrt{k^{- 1} n \log n}

$b\approx\sqrt{k^{-1}n\log n}$

ϕ

$\phi$

\begin{matrix} (*) & \underset{u < n^{'}}{⋀} T_{t_{u}}^{b} (x_{b u}, \dots, x_{b (u + 1) - 1}) \to \underset{i < l}{⋁} (\underset{j \in A_{i}}{⋀} x_{j} \land \underset{j \in B_{i}}{⋀} N_{j}) \end{matrix}

$\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^{'}

$n'$

t_{0}, \dots, t_{n^{'} - 1} \in [0, b]

$t_0,\dots,t_{n'-1}\in[0,b]$

j = b u + j^{'}

$j=bu+j'$

0 \leq j^{'} < b

$0\le j'<b$

N_{j} = T_{t_{u}}^{b - 1} (x_{b u}, \dots, x_{b u + j^{'} - 1}, x_{b u + j^{'} + 1}, \dots, x_{b (u + 1) - 1}) .

$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_{t}^{b}

$T^b_{t}$ as a monotone CNF of size

O (2^{b})

$O(2^b)$ , hence the LHS of

(*)

$(*)$ is a monotone CNF of size

O (n 2^{b})

$O(n2^b)$ . On the right-hand side, we may write

N_{j}

$N_j$ as a monotone DNF of size

O (2^{b})

$O(2^b)$ . Thus, using distributivity, each disjunct of the RHS can be written as a monotone DNF of size

O (2^{k b})

$O(2^{kb})$ , and the whole RHS is a DNF of size

O (l 2^{k b})

$O(l2^{kb})$ . It follows that

(*)

$(*)$ is an instance of our problem of size

O (l 2^{O (k b)})

$O(l2^{O(kb)})$ in

n

$n$ variables. By assumption, we may check its validity in time

O (2^{δ n + O (k b)} l^{O (1)})

$O(2^{\delta n+O(kb)}l^{O(1)})$ . We repeat this check for all

b^{n^{'}}

$b^{n'}$ choices of

\vec{t}

$\vec t$ , thus the total time is

O ((b + 1)^{n / b} 2^{δ n + O (k b)} l^{O (1)}) = O (2^{δ n + O (\sqrt{k n \log n})} l^{O (1)})

$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{aligned} s_{k} & = inf {δ : k - S A T \in D T I M E (2^{δ n})}, \\ s_{\infty} & = sup {s_{k} : k \geq 3} . \end{aligned}

$\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{aligned} s_{k}^{'} & = inf {δ : k - M o n I m p \in D T I M E (2^{δ n})}, \\ s_{\infty}^{'} & = sup {s_{k}^{'} : k \geq 3} . \end{aligned}

$\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}^{'} \leq s_{4}^{'} \leq \dots \leq s_{\infty}^{'} \leq 1

$s'_3\le s'_4\le\dots\le s'_\infty\le1$ as in the SAT case. We also have

s_{k}^{'} \leq s_{k},

$s'_k\le s_k,$ and the double-variable reduction in the question shows

s_{k} \leq 2 s_{k}^{'} .

$s_k\le2s'_k.$ Now, if we apply the construction above with constant block-size

b

$b$ , we obtain

s_{k} \leq s_{b k}^{'} + \frac{\log (b + 1)}{b},

$s_k\le s'_{bk}+\frac{\log(b+1)}b,$ hence

s_{\infty} = s_{\infty}^{'} .

$s_\infty=s'_\infty.$ In particular, SETH is equivalent to

s_{\infty}^{'} = 1

$s'_\infty=1$ , and ETH is equivalent to

s_{k}^{'} > 0

$s'_k>0$ for all

k \geq 3

$k\ge3$ .

Emil Jeřábek 3.0
źródło

Thank you for your answer! I'm curious whether it is possible to make

Φ

$\Phi$ and

Ψ

$\Psi$ constant-depth in this construction? Namely, I'm not aware whether subexponential-size constant-depth monotone Boolean formulas (or even non-monotone circuits) are known for

T_{k}^{n}

$T^n_k$ (in particular for Majority)? Of course there is a

2^{n^{Ω (1 / d)}}

$2^{n^{\Omega(1/d)}}$ lower bound for depth-

d

$d$ , but, say,

2^{\sqrt{n}}

$2^{\sqrt{n}}$ size would be OK.

Sasha Kozachinskiy

T_{k}^{n}

$T^n_k$ , and in general anything computable by polynomial-size formulas (i.e., in NC^1), has depth-

d

$d$ circuits of size

2^{n^{O (1 / d)}}

$2^{n^{O(1/d)}}$ . See e.g. cstheory.stackexchange.com/q/14700 . I will have to think if you can make them monotone, but it sounds plausible.

Emil Jeřábek 3.0

OK. First, the generic construction works fine in the monotone setting: if a function has poly-size monotone formulas, it has depth-

d

$d$ monotone circuits of size

2^{n^{O (1 / d)}} p o l y (n)

$2^{n^{O(1/d)}}\mathrm{poly}(n)$ for any

d \geq 2

$d\ge2$ . Second, for

T_{k}^{n}

$T^n_k$ specifically, it is easy to construct monotone depth-

3

$3$ circuits of size

2^{O (\sqrt{n \log n})}

$2^{O(\sqrt{n\log n})}$ by splitting the input into blocks of size

Θ (\sqrt{n \log n})

$\Theta(\sqrt{n\log n})$ .

Emil Jeřábek 3.0

Actually, pushing this idea a little bit more, it does provide an answer to the original question: assuming SETH, the lower bound holds already for

Φ

$\Phi$ monotone CNF and

Ψ

$\Psi$ monotone DNF. I will write it up later.

Emil Jeřábek 3.0

I would guess that you can divide all the variables into about

\sqrt{n}

$\sqrt{n}$ blocks

x^{1}, \dots x^{\sqrt{n}}

$x^1, \ldots x^{\sqrt{n}}$ and then write

T_{k_{1}}^{\sqrt{n}} (x^{1}) \land \dots \land T_{k_{\sqrt{n}}}^{\sqrt{n}} (x^{\sqrt{n}}) \to ϕ^{'}

$T^{\sqrt{n}}_{k_1}(x^1)\land \ldots \land T^{\sqrt{n}}_{k_\sqrt{n}}(x^{\sqrt{n}}) \to \phi^\prime$ for every

k_{1} + \dots + k_{\sqrt{n}} \leq n

$k_1 + \ldots + k_{\sqrt{n}} \le n$ . You can use

2^{\sqrt{n}}

$2^{\sqrt{n}}$ -size CNF for every threshold function. But then on a right hand side you will have not DNF but a depth-3 formula...

Sasha Kozachinskiy

Problem decydowania, czy monotoniczny CNF implikuje monotoniczny DNF

Odpowiedzi: