Masalah memutuskan apakah CNF monoton menyiratkan DNF monoton

Pertimbangkan masalah keputusan berikut

Input : CNF $\Phi$ monoton dan DNF monoton P . $\Psi$

Pertanyaan : Apakah sebuah tautologi? $\Phi \to \Psi$

Tentunya Anda dapat mengatasi masalah ini dalam waktu , di mana adalah jumlah variabel dalam dan adalah panjang input. Di sisi lain, masalah ini lengkap dengan TNP. Selain itu, pengurangan yang membentuk kelengkapan coNP juga menunjukkan bahwa, kecuali SETH gagal, tidak ada - algoritma waktu untuk masalah ini (ini berlaku untuk positif ). Inilah pengurangan ini. Biarkan menjadi CNF (non-monoton) dan biarkan menjadi variabelnya. Ganti setiap kemunculan positif oleh $O(2^n \cdot \mathrm{poly}(l))$ $n$ $\Phi \to \Psi$ $l$ $O(2^{(1/2 - \varepsilon)n} \mathrm{poly}(l))$ $\varepsilon$ $A$ $x$ $x$ $y$ dan setiap kejadian negatif oleh . Lakukan hal yang sama untuk setiap variabel. Biarkan CNF monoton yang dihasilkan menjadi . Mudah untuk melihat bahwa memuaskan jika if bukan tautologi. Pengurangan ini meledakkan jumlah variabel dengan faktor 2, yang menyiratkan batas bawah (SETH) yang disebutkan di atas. $x$ $z$ $\Phi$ $A$ $\Phi \to yz \lor \ldots$ $2^{n/2}$

Jadi ada celah antara dan waktu. Pertanyaan saya adalah apakah ada algoritma yang lebih baik atau pengurangan yang lebih baik dari SETH diketahui? $2^{n/2}$ $2^n$

Hanya dua komentar yang tampaknya terkait dengan masalah:

masalah terbalik apakah DNF monoton menyiratkan CNF monoton dapat dipecahkan secara sepele dalam waktu polinomial.
Menariknya, masalah menentukan apakah dan menghitung fungsi yang sama dapat diselesaikan dalam waktu kuasi-polinomial karena Fredman dan Khachiyan (Pada Kompleksitas Dualisasi Bentuk Normal Disjungtif Monoton, Jurnal Algoritma 21 (1996), tidak ada 3, hlm. 618-628, doi: 10.1006 / jagm.1996.0062 ) $\Phi$ $\Psi$

exp-time-algorithms boolean-formulas fine-grained Sasha Kozachinskiy
sumber

Dengan anggapan SETH, masalahnya tidak dapat diselesaikan dalam waktu $O\bigl(2^{(1-\epsilon)n}\mathrm{poly}(l)\bigr)$ untuk setiap $\epsilon>0$ .

Pertama, izinkan saya menunjukkan bahwa ini berlaku untuk masalah yang lebih umum di mana $\Phi$ dan $\Psi$ mungkin merupakan formula monoton sewenang-wenang. Dalam hal ini, ada pengurangan ctt waktu-poli dari TAUT ke masalah yang mempertahankan jumlah variabel. Mari $T^n_t(x_0,\dots,x_{n-1})$ menunjukkan fungsi threshold

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.$ Menggunakan jaringan Ajtai-Komlós-Szemerédi menyortir,

T_{t}^{n}

$T^n_t$ dapat ditulis oleh polinomial-ukuran rumus monoton, constructible dalam waktu

p o l y (n)

$\mathrm{poly}(n)$ .

Dengan rumus Boolean , kita dapat menggunakan aturan De Morgan untuk menuliskannya dalam bentuk mana adalah monoton. Kemudian $\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'$

adalah tautologi jika dan hanya jika implikasi monoton

berlaku untuk setiap

, di mana

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

Untuk implikasi kiri ke kanan, biarkan menjadi tugas memuaskan , yaitu, dengan setidaknya yang. Ada dengan yang tepat . Kemudian , dengan demikian menyiratkan $e$ $T^n_t$ $t$ $e'\le e$ $t$ $e'\models N_i\leftrightarrow\neg x_i$ $e'\models\phi$ . Karena ini adalah formula monoton, kami juga memiliki . Implikasi dari kanan ke kiri serupa. $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})$

Sekarang, izinkan saya kembali ke masalah semula. Saya akan menunjukkan yang berikut ini: jika masalahnya dapat diselesaikan dalam waktu , maka untuk , -DNF-TAUT (atau setiap akhir, -SAT) dapat dipecahkan dalam waktu $2^{\delta n}\mathrm{poly}(l)$ $k$ $k$ $k$ . Ini menyiratkanjika SETH bertahan. $2^{\delta n+O(\sqrt{kn\log n})}\mathrm{poly}(l)$ $\delta\ge1$

Jadi, anggap kita diberi -DNF mana untuk setiap . Kami membagi variabel menjadi blok ukuran $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$

masing-masing. Dengan argumen yang sama seperti di atas,

adalah tautologi jika dan hanya jika implikasinya

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

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

ϕ

$\phi$

berlaku untuk setiap

-tuple

, di mana untuk

, kita mendefinisikan

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

Kita bisa menulis

sebagai monoton CNF ukuran

, maka LHS dari

adalah monoton CNF ukuran

. Di sisi kanan, kita dapat menulis

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

T_{t}^{b}

$T^b_{t}$

O (2^{b})

$O(2^b)$

(*)

$(*)$

O (n 2^{b})

$O(n2^b)$

N_{j}

$N_j$ sebagai DNF monoton ukuran

. Jadi, dengan menggunakan distributivity, masing-masing terpisah dari RHS dapat ditulis sebagai DNF monoton ukuran

, dan seluruh RHS adalah DNF ukuran

. Oleh karena itu

adalah sebuah contoh dari masalah kita ukuran

variabel. Dengan asumsi, kami dapat memeriksa validitasnya dalam waktu

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$

. Kami mengulangi pemeriksaan ini untuk semua

pilihan

, sehingga total waktu adalah

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$

seperti diklaim.

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

Kami mendapatkan koneksi yang lebih ketat dengan (S) ETH dengan mempertimbangkan versi lebar-terbatas masalah: untuk setiap , mari -MonImp menunjukkan batasan masalah di mana adalah -CNF, dan adalah -DNF. (S) ETH menyangkut konstanta $k\ge3$ $k$ $\Phi$ $k$ $\Psi$ $k$

\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*}$

\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*}$

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

$s'_3\le s'_4\le\dots\le s'_\infty\le1$

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_{b k}^{'} + \frac{\log (b + 1)}{b},

$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 mendukung Monica
sumber

Φ

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

T_{k}^{n}

$T^n_k$

d

$d$

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

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

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

Φ

$\Phi$

Ψ

$\Psi$

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

Masalah memutuskan apakah CNF monoton menyiratkan DNF monoton

Jawaban: