Mengapa SIKLUS HAMILTONIAN begitu berbeda dari PERMANEN?

Polinom adalah proyeksi monoton dari polinom jika = poli , dan ada penugasan $f(x_1,\ldots,x_n)$ $g(y_1,\ldots,y_m)$ $m$ $(n)$ sedemikian rupa sehingga . Yaitu, adalah mungkin untuk mengganti setiap variabel dari dengan variabel atau konstanta atau sehingga polinomial yang dihasilkan bertepatan dengan . $\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ $f(x_1,\ldots,x_n)=g(\pi(y_1),\ldots,\pi(y_m))$ $y_j$ $g$ $x_i$ $0$ $1$ $f$

Saya tertarik (alasan) perbedaan antara PER polinomial permanen dan siklus Hamiltonian polinomial HAM: mana penjumlahan pertama adalah semua permutasi

{PER}_{n} (x) = \sum_{h} \prod_{i = 1}^{n} x_{i, h (i)} and {HAM}_{n} (x) = \sum_{h} \prod_{i = 1}^{n} x_{i, h (i)}

$\mbox{PER}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}\ \ \ \ \mbox{and} \ \ \ \ \mbox{HAM}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}$

, dan yang kedua hanya di atas semuapermutasisiklik

h : [n] \to [n]

$h:[n]\to[n]$

h : [n] \to [n]

$h:[n]\to[n]$

Pertanyaan: Mengapa HAM bukan proyeksi monoton PER? Atau masih?

Saya tidak meminta bukti , hanya untuk alasan intuitif.

Motivasi: sirkuit monoton terbesar yang diketahui lebih rendah untuk PER (dibuktikan oleh Razborov) tetap "hanya" . Di sisi lain, hasil Valiant menyiratkan bahwa mana dengan penjumlahan adalah atas semua himpunan bagian dari ukuran $n^{\Omega(\log n)}$

CLIQUE_{n} is a monotone projection of HAM_{m}

$\mbox{CLIQUE$_n$ is a monotone projection of HAM$_{m}$}$

{CLIQUE}_{n} (x) = \sum_{S} \prod_{i < j \in S} x_{i, j}

$\mbox{CLIQUE}_n(x)=\sum_{S}\prod_{i < j\in S}x_{i,j}$

S \subseteq [n]

$S\subseteq [n]$

. Saya sendiri tidak bisa mendapatkan reduksi "sederhana, langsung" dari hasil-hasil umum ini, tetapiAlon dan Boppanamengklaim (dalam Bagian 5) yang sudah

sudah cukup untuk pengurangan ini.

| S | = \sqrt{n}

$|S|=\sqrt{n}$

m = 25 n^{2}

$m=25n^2$

Tapi tunggu: diketahui bahwa CLIQUE membutuhkan sirkuit monoton ukuran (pertama kali dibuktikan oleh Alon dan Boppana menggunakan metode Razborov). $2^{n^{\Omega(1)}}$

Jadi, jika HAM adalah proyeksi monoton PER, kita akan memiliki batas bawah juga untuk PER. $2^{n^{\Omega(1)}}$

Sebenarnya, mengapa HAM bahkan bukan proyeksi non-monoton PER? Selama semiring boolean, yang pertama adalah NP -Lengkap, sedangkan yang kedua adalah di P . Tapi kenapa? Di mana tempat siklik untuk permutasi membuatnya sangat istimewa?

PS Satu perbedaan yang jelas bisa jadi: HAM mencakup [n] hanya dengan satu siklus (panjang), sedangkan PER dapat menggunakan siklus yang terpisah untuk ini. Jadi, untuk memproyeksikan PER ke HAM arah yang sulit tampaknya adalah: memastikan bahwa tidak adanya siklus Hamiltonian menyiratkan tidak adanya tutupan dengan siklus terpisah dalam grafik baru. Apakah ini alasan HAM tidak menjadi proyeksi PER?

PPS Sebenarnya, Valiant terbukti hasil yang lebih mengesankan: setiap polinomial dengan , yang koefisien adalah p-waktu dihitung , adalah proyeksi (tidak harus monoton jika algo adalah non-monoton) dari HAM untuk = poli $f(x)=\sum_{u\subseteq [n]}c_u\prod_{i\in u}x_i$ $c_u\in\{0,1\}$ $c_u$ $_m$ $m$ $(n)$ . PER juga memiliki properti ini, tetapi hanya atas bidang karakteristik . Jadi, dalam pengertian ini, HAM dan PER yang memang "mirip", kecuali kita tidak dalam GF (2) di mana, sebagai Bruno ingat, PER ternyata DETERMINAN, dan mudah. $\neq 2$

cc.complexity-theory circuit-complexity lower-bounds arithmetic-circuits Stasys
sumber

Saya punya sedikit pertanyaan di luar topik. Bolehkah saya bertanya mengapa PERMANEN dalam P lebih dari semiring boolean? Saya tidak mengetahui adanya algoritma seperti itu.

caozhu

@caozhu: Ini hanya karena PERMANEN sama dengan DETERMINAN atas semiring boolean. Algoritma tersebut kemudian adalah algoritma PENENTUAN.

Bruno

@ Bruno: tidak cukup. Anda benar jika kita berada di bidang GF (2); maka kita bisa menggunakan, katakanlah, Gauss. Namun, boolean

sirkuit untuk PER ukuran sekitar

dapat dibangun menggunakan algoritma Hopcroft-Karp untuk pencocokan maksimum, atau hanya Floyd-Fulkerson algoritma cacat maksimal.

{\lor, \land, \neg}

$\{\lor,\land,\neg\}$

n^{5 / 2}

$n^{5/2}$

Stasys

Berikut ini adalah bukti atas setiap cincin dengan karakteristik nol bahwa polinomial siklus Hamilton bukanlah proyeksi monoton ukuran polinomial dari permanen. Ide dasarnya adalah bahwa proyeksi monoton polinomial dengan koefisien nonnegatif mengarah ke Newton polytope yang satu merupakan perumusan diperpanjang dari Newton polytope yang lain, dan kemudian menerapkan batas bawah baru-baru ini pada formulasi yang diperluas.

$f(x_1,\dotsc,x_n)$ $g(y_1,\dotsc,y_m)$ $f$ $g$ $\pi$ $\pi$ $g$ $f$

$New(f)$ $f$ $New(g)$

$New(f)$ $\mathbb{R}^m$ $\leq n+m$ $n+m$ $New(g)$

$e_1,\dotsc,e_m$ $\mathbb{R}^m$ $New(g)$ $\mathbb{R}^m$ $(e_1,\dotsc,e_m)$ $y_1^{e_1} \dotsb y_m^{e_m}$ $i$ $\pi(y_i)=0$ $New(g)$ $\{e_i = 0\}$ $y_i$ $m$ $P$ $\pi$ $L_{\pi}\colon \mathbb{R}^{m} \to \mathbb{R}^{n}$ $L_{\pi}(P) = New(f)$ $New(f)$ $n+m$ $P$ $m$ $L_{\pi}$ $n$ $x_i$

$f$ $n$ $g$ $m$ $f$ $g$ $e_{ij}$ $m$

$2^{n^{\Omega(1)}}$ $m$ $L_{\pi}$

$f$ $g$ $\pi$ $L_{\pi}$ $New(f)$

$\mathsf{P}$ $\mathsf{NP}$

Joshua Grochow
sumber

argumen yang sangat bagus. Inilah yang saya cari! Memang, formulasi LP diperpanjang mensimulasikan proyeksi Valiant (setidaknya monoton).

Stasys

Mengapa SIKLUS HAMILTONIAN begitu berbeda dari PERMANEN?

Jawaban: