El problema de decidir si un CNF monótono implica un DNF monótono

Suponiendo SETH, el problema no se puede resolver en el tiempo para cualquier . $O\bigl(2^{(1-\epsilon)n}\mathrm{poly}(l)\bigr)$ $\epsilon>0$

Primero, permítanme mostrar que esto es cierto para el problema más general donde y pueden ser fórmulas monótonas arbitrarias. En este caso, hay una reducción ctt de tiempo múltiple de TAUT al problema que conserva el número de variables. Deje que denote la función de umbral Utilizando la red de clasificación Ajtai – Komlós – Szemerédi, puede escribirse mediante una fórmula monótona de tamaño polinómico, construible en el tiempo . $\Phi$ $\Psi$ $T^n_t(x_0,\dots,x_{n-1})$

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

Dada una fórmula booleana , podemos usar las reglas de De Morgan para escribirla en la forma donde es monótono. Entonces es una tautología si y solo si las implicaciones monótonas son válidos para cada , donde $\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'$

ϕ (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}).$

Para la implicación de izquierda a derecha, deja ser una misión satisfacer , es decir, con al menos queridos. Existe con exactamente unos. Entonces , entonces implica . Como se trata de una fórmula monótona, también tenemos . La implicación de derecha a izquierda es similar. $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})$

Ahora, déjame volver al problema original. Mostraré lo siguiente: si el problema se puede resolver en el tiempo , entonces para cualquier , -DNF-TAUT (o dually, -SAT) se puede resolver en tiempo . Esto implica si se mantiene . $2^{\delta n}\mathrm{poly}(l)$ $k$ $k$ $k$ $2^{\delta n+O(\sqrt{kn\log n})}\mathrm{poly}(l)$ $\delta\ge1$

Entonces, supongamos que se nos da un -DNF donde para cada . Dividimos las variables en bloques de tamaño cada uno. Por el mismo argumento anterior, es una tautología si y solo si las implicaciones son válidos para cada -tuple , donde para cualquier $k$

ϕ = \underset{yo < l}{⋁} (\underset{j \in {UN}_{yo}}{⋀} X_{j} \land \underset{j \in {si}_{yo}}{⋀} \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{tu < {norte}^{'}}{⋀} T_{t_{tu}}^{si} (X_{si tu}, ..., X_{si (tu + 1) - 1}) \to \underset{yo < l}{⋁} (\underset{j \in {UN}_{yo}}{⋀} X_{j} \land \underset{j \in {si}_{yo}}{⋀} {norte}_{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'$ , , definimos Podemos escribir como un CNF monótono de tamaño , por lo tanto, el LHS de es un CNF monótono de tamaño . En el lado derecho, podemos escribir como un DNF monótono de tamaño . Por lo tanto, utilizando la distributividad, cada disyunción del RHS se puede escribir como un DNF monótono de tamaño , y todo el RHS es un DNF de tamaño . De ello se deduce que es una instancia de nuestro problema de tamaño en

0 \leq j^{'} < b

$0\le j'<b$

{norte}_{j} = T_{t_{tu}}^{si - 1} (X_{si tu}, ..., X_{si tu + j^{'} - 1}, X_{si tu + j^{'} + 1}, ..., X_{si (tu + 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}).$

T_{t}^{b}

$T^b_{t}$

O (2^{b})

$O(2^b)$

(*)

$(*)$

O (n 2^{b})

$O(n2^b)$

N_{j}

$N_j$

O (2^{b})

$O(2^b)$

O (2^{k b})

$O(2^{kb})$

O (l 2^{k b})

$O(l2^{kb})$

(*)

$(*)$

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

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

n

$n$ variables Por supuesto, podemos verificar su validez en el tiempo . Repetimos esta comprobación para todas opciones de , por lo tanto, el tiempo total es como se afirma.

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

$O(2^{\delta n+O(kb)}l^{O(1)})$

b^{n^{'}}

$b^{n'}$

\vec{t}

$\vec t$

O ((si + 1)^{norte / / si} 2^{δ norte + O (k si)} l^{O (1)}) = O (2^{δ norte + O (\sqrt{k norte Iniciar sesión norte})} 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)$

Obtenemos una conexión más estrecha con el (S) ETH al considerar la versión de ancho limitado del problema: para cualquier , dejemos que -MonImp denote la restricción del problema donde es un -CNF y es un -DNF. La (S) ETH se refiere a las constantes Del mismo modo, definamos Claramente, $k\ge3$ $k$ $\Phi$ $k$ $\Psi$ $k$

\begin{aligned} s_{k} & = inf {δ : k - S UN T \in re T yo METRO mi (2^{δ norte})}, \\ s_{\infty} & = cenar {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*}$

\begin{aligned} s_{k}^{'} & = inf {δ : k - METRO o norte yo metro pag \in re T yo METRO mi (2^{δ norte})}, \\ s_{\infty}^{'} & = cenar {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*}$

s_{3}^{'} \leq s_{4 4}^{'} \leq \dots \leq s_{\infty}^{'} \leq 1

$s'_3\le s'_4\le\dots\le s'_\infty\le1$ como en el caso SAT. También tenemos y la reducción de doble variable en la pregunta muestra Ahora, si aplicamos la construcción anterior con un tamaño de bloque constante , obtenemos tanto En particular, SETH es equivalente a , y ETH es equivalente a para todos los .

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

$s'_k\le s_k,$

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

$s_k\le2s'_k.$

b

$b$

s_{k} \leq s_{si k}^{'} + \frac{Iniciar sesión (si + 1)}{si},

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

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

$s_\infty=s'_\infty.$

s_{\infty}^{'} = 1

$s'_\infty=1$

s_{k}^{'} > 0

$s'_k>0$

k \geq 3

$k\ge3$

Emil Jeřábek apoya a Monica
fuente

¡Gracias por su respuesta! Tengo curiosidad por saber si es posible hacer y de profundidad constante en esta construcción. Es decir, no sé si las fórmulas booleanas monótonas de profundidad constante de tamaño subexponencial (o incluso los circuitos no monótonos) se conocen para (en particular para Mayoría). Por supuesto, hay un límite inferior para profundidad- , pero, digamos, el tamaño estaría bien.

Φ

$\Phi$

Ψ

$\Psi$

T_{k}^{n}

$T^n_k$

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

$2^{n^{\Omega(1/d)}}$

d

$d$

2^{\sqrt{n}}

$2^{\sqrt{n}}$

Sasha Kozachinskiy

T_{k}^{n}

$T^n_k$ , y en general cualquier cosa computable por fórmulas de tamaño polinómico (es decir, en NC ^ 1), tiene circuitos de profundidad de tamaño . Consulte, por ejemplo, cstheory.stackexchange.com/q/14700 . Tendré que pensar si puedes hacerlos monótonos, pero suena plausible.

d

$d$

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

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

Emil Jeřábek apoya a Monica el

OKAY. Primero, la construcción genérica funciona bien en la configuración monótona: si una función tiene fórmulas monótonas de tamaño polivinílico, tiene circuitos monotonos de profundidad de tamaño para cualquier . En segundo lugar, para específicamente, es fácil construir circuitos monótonos de profundidad- de tamaño dividiendo la entrada en bloques de tamaño .

d

$d$

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

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

d \geq 2

$d\ge2$

T_{k}^{n}

$T^n_k$

3

$3$

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

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

Θ (\sqrt{n \log n})

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

Emil Jeřábek apoya a Monica el

En realidad, al impulsar esta idea un poco más, proporciona una respuesta a la pregunta original: suponiendo que SETH, el límite inferior ya es válido para monotone CNF y monotone DNF. Lo escribiré más tarde.

Φ

$\Phi$

Ψ

$\Psi$

Emil Jeřábek apoya a Monica el

Supongo que puede dividir todas las variables en aproximadamente bloques y luego escribir por cada . Puede usar CNF de -size para cada función de umbral. Pero luego, en el lado derecho, no tendrá DNF sino una fórmula de profundidad 3 ...

\sqrt{n}

$\sqrt{n}$

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

$x^1, \ldots x^{\sqrt{n}}$

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$

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

$k_1 + \ldots + k_{\sqrt{n}} \le n$

2^{\sqrt{n}}

$2^{\sqrt{n}}$

Sasha Kozachinskiy

El problema de decidir si un CNF monótono implica un DNF monótono

Respuestas: