Apakah Norbert Blum 2017 bukti bahwa

Norbert Blum baru-baru ini diposting 38-halaman bukti bahwa $P \ne NP$ . Apakah itu benar?

Juga pada topik: di mana lagi (di internet) kebenarannya sedang dibahas?

Catatan: fokus teks pertanyaan ini telah berubah seiring waktu. Lihat komentar pertanyaan untuk detailnya.

Seperti disebutkan di sini sebelumnya, contoh Tardos dengan jelas membantah buktinya; itu memberikan fungsi monoton, yang setuju dengan CLIQUE pada T0 dan T1, tetapi yang terletak pada P. Ini tidak akan mungkin jika buktinya benar, karena buktinya berlaku untuk kasus ini juga. Namun, bisakah kita menunjukkan kesalahannya? Inilah, dari sebuah posting di blog lipton, apa yang tampaknya menjadi tempat buktinya gagal:

Kesalahan tunggal adalah satu titik halus dalam bukti Teorema 6, yaitu pada Langkah 1, di halaman 31 (dan juga 33, di mana kasus ganda dibahas) - klaim yang tampaknya jelas bahwa $C'_g$ berisi semua klausa yang sesuai yang terkandung dalam dll, tampaknya salah.$CNF'(g)$

Untuk menjelaskan hal ini secara lebih rinci, kita perlu masuk ke metode pembuktian dan pendekatan Berg dan Ulfberg, yang menyatakan kembali bukti asli Razborov tentang kompleksitas monoton eksponensial untuk CLIQUE dalam hal sakelar DNF / CNF. Ini adalah bagaimana saya melihatnya:

Untuk setiap node / gerbang dari rangkaian logika β (hanya berisi biner ATAU / DAN gerbang), bentuk normal konjungtif C N F ( g ) , bentuk normal disjungtif D N F ( g ) , dan aproksimasi C k g dan D r g terpasang. C N F dan D N F hanyalah bentuk-bentuk normal keluaran disjungtif dan konjungtif yang sesuai. D r g dan C k $g$$\beta$$CNF(g)$$DNF(g)$$C^k_g$$D^r_g$$CNF$$DNF$$D^r_g$$C^k_g$juga merupakan bentuk disjungtif dan konjungtif, tetapi dari beberapa fungsi lain, "mendekati" output gerbang. Namun mereka wajib memiliki jumlah dibatasi variabel dalam setiap monomial untuk (kurang dari r konstan) dan di setiap klausul untuk$D^r_g$ (kurang dari k konstan).$C^k_g$

Ada gagasan tentang "kesalahan" yang diperkenalkan dengan perkiraan ini. Bagaimana kesalahan ini dihitung? Kami hanya tertarik pada beberapa set T0 input yang total fungsinya mengambil nilai 0, dan T1 input yang total fungsinya mengambil nilai 1 ("janji"). Sekarang di setiap gerbang, kita hanya melihat input dari T0 dan T1, yang dihitung dengan benar (oleh dan C N F ( g ) , yang mewakili fungsi yang sama - keluaran gerbang g dalam β ) di pintu gerbang output, dan melihat berapa banyak kesalahan / kesalahan adalah untuk C k g dan$DNF(g)$$CNF(g)$$g$$\beta$$C^k_g$$D^r_g$, dibandingkan dengan itu. Jika gerbang adalah konjungsi, maka keluaran gerbang mungkin menghitung lebih banyak input dari T0 dengan benar (tetapi input yang dihitung dengan benar dari T1 kemungkinan menurun). Untuk , yang didefinisikan sebagai konjungsi sederhana, tidak ada kesalahan baru namun pada semua masukan tersebut. Sekarang, D r g didefinisikan sebagai saklar CNF / DNF dari C k g , jadi mungkin ada sejumlah kesalahan baru pada T0, datang dari switch ini. Pada T1 juga, tidak ada kesalahan baru pada C k g - setiap kesalahan harus hadir di kedua input gerbang, dan juga di D r $C^k_g$$D^r_g$$C^k_g$$C^k_g$$D^r_g$, sakelar tidak memperkenalkan kesalahan baru pada T1. Analisis untuk gerbang OR adalah ganda.

Jadi jumlah kesalahan untuk aproksimasi akhir dibatasi oleh jumlah gerbang dalam , dikalikan jumlah kesalahan maksimal yang dimungkinkan oleh sakelar CNF / DNF (untuk T0), atau oleh sakelar DNF / CNF (untuk T1). Tetapi jumlah total kesalahan harus "besar" dalam setidaknya satu kasus (T0 atau T1), karena ini adalah properti dari bentuk normal konjungtif positif dengan klausa yang dibatasi oleh k , yang merupakan wawasan kunci dari bukti asli Razborov (Lemma). 5 di koran Blum).$\beta$$k$

Jadi apa yang Blum lakukan untuk mengatasi negasi (yang didorong ke level input, sehingga sirkuit masih hanya berisi gerbang biner OR / AND)?$\beta$

Idenya adalah untuk membentuk CNF / DNF dan DNF / CNF switch secara terbatas, hanya ketika semua variabel positif. Kemudian switch akan bekerja PERSIS seperti dalam kasus Berg dan Ulfberg, memperkenalkan jumlah kesalahan yang sama. Ternyata ini adalah satu-satunya kasus yang perlu dipertimbangkan.

Jadi, ia mengikuti garis Berg dan Ulfberg, dengan beberapa perbedaan. Alih-alih melampirkan , D N F ( g ) , C k g dan D r g ke setiap gerbang g dari sirkuit β , ia melampirkan modifikasinya, C N F ′ ( g ) , D N F ′ ( g ) , C ' k g dan $CNF(g)$$DNF(g)$$C^k_g$$D^r_g$$g$$\beta$$CNF'(g)$$DNF'(g)$${C'}^k_g$ , yaitu bentuk normal "mengurangi" disjungtif dan penghubung, yang didefinisikan berbeda dariCNF(g)danDNF(g)oleh "aturan penyerapan", menghapus variabel menegasikan dari semua monomials campuran / klausul ( ia juga menggunakan untuk operasi tujuan ini yang dilambangkan oleh R, menghilangkan beberapa monomial / klausa sepenuhnya; seperti yang telah kita bahas sebelumnya, definisi R yang agak informal bukan masalah, R dapat dibuat tepat sehingga diterapkan di setiap gerbang tetapi apa dihapus tidak hanya tergantung pada dua input sebelumnya tetapi pada seluruh rangkaian yang mengarah ke gerbang itu), dan aproksimatornyaC′${D'}^r_g$$CNF(g)$$DNF(g)$ danD' r g , bahwa ia juga memperkenalkan.${C'}^r_g$${D'}^r_g$

Dia menyimpulkan, dalam Teorema 5, bahwa untuk fungsi monoton, mengurangi dan D N F ′ akan benar-benar menghitung 1 dan 0 pada set T1 dan T0, pada simpul akar g 0 (yang outputnya adalah output dari seluruh fungsi dalam β ). Teorema ini, saya percaya, benar.$CNF'$$DNF'$$g_0$$\beta$

Sekarang tiba penghitungan kesalahan. Saya percaya kesalahan pada setiap node dimaksudkan untuk dihitung dengan membandingkan pengurangan dan D N F ′ ( g ) (yang sekarang mungkin dua fungsi berbeda), dengan C ′ r g dan D ′ k g saat ia mendefinisikan mereka. Definisi aproksimator definisi parrot dari C N F ′ dan D N F $CNF'(g)$$DNF'(g)$${C'}^r_g$${D'}^k_g$$CNF'$$DNF'$(Langkah 1) ketika mencampur variabel dengan variabel yang dinegasikan, tetapi ketika dia berurusan dengan variabel positif, dia menggunakan saklar seperti dalam kasus Berg dan Ulfberg (Langkah 2). Dan memang, pada Langkah 2 ia akan memperkenalkan jumlah kesalahan yang mungkin sama seperti sebelumnya (itu adalah saklar yang sama, dan semua variabel yang terlibat positif).

Tapi buktinya salah pada Langkah 1. Saya pikir Blum membingungkan , γ 2 , yang benar-benar datang, seperti yang didefinisikannya, dari aproksimasi sebelumnya (untuk gerbang h 1 , h 2 ), dengan bagian positif C N F ′ β ( h 1 ) dan C N F ′ β ( h 2 ) . Ada perbedaan, dan karenanya, pernyataan " C ′ g berisi masih semua klausa yang terkandung dalam C N F $\gamma_1$$\gamma_2$$h_1$$h_2$$CNF'_\beta(h_1)$$CNF'_\beta(h_2)$$C_g'$ sebelum perkiraan gerbang g yang menggunakan klausa dalam γ ′ 1 atau γ ′ 2 "tampaknya salah secara umum.$CNF'_\beta(g)$$\gamma_1'$$\gamma_2'$

Saya akrab dengan Alexander Razborov yang pekerjaan sebelumnya sangat penting dan berfungsi sebagai dasar untuk bukti Blum. Saya beruntung dapat bertemu dengannya hari ini dan tidak membuang waktu untuk meminta pendapatnya tentang semua masalah ini, apakah dia bahkan telah melihat buktinya atau tidak dan apa pendapatnya tentang hal itu jika dia melakukannya.

Yang mengejutkan saya, dia menjawab bahwa dia memang menyadari kertas Blum tetapi tidak mau membacanya pada awalnya. Tetapi karena semakin banyak kemasyhuran diberikan kepadanya, ia mendapatkan kesempatan untuk membacanya dan mendeteksi cacat dengan segera: yaitu bahwa alasan yang diberikan oleh Berg dan Ulfberg sangat cocok untuk fungsi Tardos, dan karena memang demikian, bukti Blum tentu diperlukan. salah karena bertentangan dengan inti Teorema 6 dalam makalahnya.

Ini diposting sebagai jawaban komunitas karena (a) itu bukan kata-kata saya sendiri, tetapi kutipan dari Luca Trevisan di platform media sosial atau dari orang lain tanpa akun CSTheory.SE; dan (b) siapa pun harus merasa bebas untuk memperbarui ini dengan informasi terbaru yang relevan.

Mengutip Luca Trevisan dari pos publik Facebook (14/08/2017), menjawab pertanyaan tentang makalah ini yang ditanyakan oleh Shachar Lovett :

Fungsi Andreev, yang diklaim memiliki kompleksitas sirkuit superpolinomial (abstrak, kemudian bagian 7), hanyalah interpolasi polinomial univariat di bidang terbatas, yang, jika saya tidak melewatkan sesuatu, dapat dipecahkan dengan eliminasi Gaussian

Sebenarnya, ini belum tentu titik di mana buktinya gagal; Luca kemudian menjawab yang berikut (15/08/2017), setelah pertanyaan terkait dengan komentar Andrew di bawah:

Anda benar, teman-teman, saya salah mengerti definisi fungsi Andreev: tidak jelas bahwa itu mengurangi interpolasi polinomial

Karl Wimmer mengomentari poin yang diajukan oleh Gustav Nordh (direproduksi dengan izin Karl):

Untuk menambah ini, saya tidak melihat mengapa, dari dua paragraf pertama dari bukti Teorema 5, kita dapat menyimpulkan bahwa menghitung f . Saya hanya melihat semacam satu sisi-ness yang D N F ' ( g 0 ) menghitung fungsi sehingga f = $\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$$f = 1$ berarti bahwa fungsi ini juga 1.

Paragraf ketiga tidak membantu saya: pasti dan sakelar DNF / CNF-nya menghitung fungsi yang sama, tetapi tidak segera mengikuti bahwa sakelar DNF / CNF menghitung f (karena D N F ′ ( g 0 ) mungkin tidak), jadi kami tidak dapat membuat kesimpulan tentang f- klausa.$\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$$f$

(Selain: keberpihakan satu sisi ini konsisten dengan contoh Gustav di atas.)

Dari sudut pandang yang berbeda, tentunya jaringan standar yang menghitung fungsi monoton dapat menghitung fungsi non-monoton pada simpul internal. Teorema 5 tidak berlaku untuk fungsi non-monoton, sehingga tidak mungkin benar menghitung sub-fungsi dalam jaringan yang simpul output g (yang akan terjadi bagi banyak fungsi non-monoton). Karena itu, saya tidak yakin bahwa pembangunan induktif ini D N F ' ( g 0 ) tentu akan benar pada akhirnya.$\mathrm{DNF'}(g)$$g$$\mathrm{DNF'}(g_0)$

Jika saya benar-benar tak berdaya di sini, tolong beri tahu saya!

Dari pengguna anonim, sebagai reaksi terhadap poin Karl:

DNF 'dan CNF' hanyalah DNF dan CNF untuk f, di mana pembatalan literal yang berlawanan dilakukan, sehingga mengurangi mereka menjadi bentuk yang lebih pendek. Ini juga dijelaskan dalam makalah, dan itu agak rumit dari definisi tetapi itu adalah apa itu. Teorema 5 bukan masalah, daging ada di Teorema 6.

Dan jawaban oleh Karl (yang saya reproduksi lagi di sini):

Saya mengerti apa yang dikatakan anon (terima kasih!); komentar saya tidak menanggapi dengan baik kebingungan saya. Jika monoton dan dihitung pada g 0 , tidak apa-apa untuk mengambil D N F ( g 0$f$$g_0$$\mathrm{DNF}(g_0)$ , menerapkan penyerapan dan operator , dan D N F ′ ( g 0 ) yang dihasilkan mewakili f . Menggunakan ini "satu-shot" konstruksi, Teorema 5 baik-baik saja - untuk Teorema 6. Saya dipoles definisi D N F ' ( g 0$R$$\mathrm{DNF'}(g_0)$$f$$\mathrm{DNF'}(g_0)$

Apa yang saya tidak bisa melihat mengapa gerbang-by-pintu gerbang menerapkan penyerapan-dan- -seperti-you-go pembangunan D $R$pada halaman 27-28 melakukan hal yang sama. Ini tampaknya perlu untuk analisis gerbang-demi-gerbang dalam Teorema 6 agar berhasil, kecuali kesalahan dari konstruksi ini dicatat. Maksud saya, tidak setiap fungsi bahkan dapat diwakili oleh DNF dengan istilah dengan hanya non-dinegasikan atau dinegasikan literal, tetapi untuk setiap nodeg, D N F ′ (g)tampaknya selalu memiliki formulir ini. Bagaimana jika ada simpulgdi jaringan saya sehingga r e s$\mathrm{DNF'}(g_0)$$g$$\mathrm{DNF'}(g)$$g$ tidak memiliki perwakilan seperti itu?$\mathrm{res}(g)$

(Poin kecil (?) Lainnya: Saya tidak melihat apa yang lakukan dalam konstruksi gerbang-demi-gerbang saat Anda berjalan; pada 1.-4., Sepertinya α sudah merupakan konstruksi DNF standar, tetapi dengan penyerapan dan R diterapkan.)$R$$\alpha$$R$

(jawaban dari anon) Saya setuju bahwa ketidakjelasan dalam definisi R mungkin menjadi masalah di bagian 6. R tidak didefinisikan secara eksplisit, dan kecuali tindakannya entah bagaimana tergantung pada seluruh DNF (dan bukan pada nilai-nilai DNF 'di gerbang secara induktif) , mungkin ada masalah. Bukti Deolalikar memiliki masalah yang sama - dua definisi berbeda bingung. Di sini, setidaknya kita tahu apa yang dimaksud dengan DNF ', dan jika ini adalah sumber masalah di bagian 6, bisa mudah dilacak. Saya tidak masuk ke bagian 6 namun, itu membutuhkan bukti pemahaman oleh penaksir oleh Berg dan Ulfberg yang dijelaskan dalam bagian 4, akhirnya terkait dengan konstruksi Razborov dari tahun 1985, yang tidak mudah.

Penjelasan bagaimana R bekerja:

Ketika R diterapkan dalam beberapa langkah, itu hanya membatalkan istilah yang, PADA LANGKAH YANG, akan berisi literal yang berlawanan (kita mungkin perlu melacak literal negatif). Sebagai contoh, mari kita evaluasi sebagai ( ( x ∨ y ) ∧ ( ¬ x ∨ y ) ) ∧ ( x ∨ ¬ y ) pertama, untuk menghitung DNF 'pada simpul AND pertama, kita mendapatkan

$$(x\lor y) \land (\lnot x \lor y) \land (x \lor \lnot y)$$ $$((x\lor y) \land (\lnot x \lor y))\land (x \lor \lnot y)$$ sebelum menerapkan R, tetapi setelah menerapkan R kita kehilangan x pertamadari braket pertama, dan mendapatkan ( y ) ( x ∧ y ) ∨ ( y ) , (di mana y pertamamungkin memiliki NOT virtual x jika kita melacaknya). Kemudian terapkan AND kedua, untuk mendapatkan ( ( y ) ∨ $$(x\lor y) \lor ((x\land y)\lor (y\land y))$$ $x$) ∨ ( y ) ) ∨ ( ( x ∧ y ) ∨ ( x ∧ y ) ∨ $$(y) \lor (x\land y)\lor (y),$$ $y$$x$ tetapi kemudian R menghapus seluruh braket pertama karena memiliki virtual TIDAK y hadir (dalam hal ini kami tidak tidak perlu melacak langkah-langkah sebelumnya, tapi mungkin kita perlu secara umum), meninggalkan ( ( x ∧ y ) ∨ ( x ∧ y ) ∨ ( x ∧ y $$((y) \lor (x\land y)\lor (y)) \lor ((x\land y)\lor (x\land y) \lor (x\land y)),$$ atau secara sederhana ( x ∧ y $$((x\land y)\lor (x\land y) \lor (x\land y))$$ $$(x\land y)$$

Kebenaran bukti yang diklaim sedang dibahas di blog Luca Trevisan: https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal- np /

Secara khusus "anon" memposting komentar yang relevan berikut:

"Tardos mengamati bahwa argumen Razborov dan Alon-Boppana terbawa ke fungsi yang dikomputasi oleh sirkuit non-monoton ukuran polinom (fungsi adalah varian kecil pada perkiraan fungsi grafik theta Lovasz). Jika argumen Berg dan Ulfberg juga berlaku untuk fungsi Tardos (yang kemungkinan secara intuitif, karena bukti mereka tampaknya didasarkan pada bukti Razborov) maka jelas bahwa klaim Blum saat ini tidak dapat benar. Sayangnya, penulis tidak membahas hal ini. "

Pada pertanyaan langsung dari "Mikhail", Alexander Razborov mengonfirmasi hal ini (lihat posting Mikhail): alasan yang diberikan oleh Berg dan Ulfberg sangat cocok untuk fungsi Tardos, dan karena memang demikian, bukti Blum tentu salah karena bertentangan dengan nukleus dari teorema keenam di makalahnya.- A. Razborov

Menurut pendapat saya ini pasti menyelesaikan pertanyaan apakah kertas itu benar atau tidak (itu TIDAK benar!). Penting juga untuk dicatat bahwa tampaknya sulit untuk memperbaiki buktinya karena metode buktinya sendiri tampaknya cacat.

Pembaruan (2017/08/30) Norbert Blum memposting komentar berikut di halaman arXiv-nya:

Buktinya salah. Saya akan menguraikan dengan tepat apa kesalahannya. Untuk melakukan ini, saya perlu waktu. Saya akan meletakkan penjelasan di beranda saya

Gustav Nordh dikomentari oleh Theorem 5 (halaman 29). Secara khusus, fungsi

$1$$x$$y$$1$$\beta$$x$$y$$\beta$$g_0$ .

$DNF'_{\beta}(g_0)$$\beta$

$DNF'_{\beta}(g_0)$$f$$DNF'_{\beta}(g_0)$$x$$f$$x=1$$f(x,y)=1$$R$

Bisakah seseorang menggunakan daftar decoding dari kode Reed-Solomon untuk menunjukkan fungsi POLY Andreev dalam P, mirip dengan cara Sivakumar dalam keanggotaannya yang sebanding dengan kertas ? Atau apakah fungsi POLY dikenal sebagai NP-complete?

Dia telah memperbarui arXivnya untuk mengatakan bahwa buktinya salah:

Buktinya salah. Saya akan menguraikan dengan tepat apa kesalahannya. Untuk melakukan ini, saya perlu waktu. Saya akan meletakkan penjelasan di beranda saya.

Blog Lipton dan Regan di sini memiliki diskusi tingkat tinggi yang bagus dengan komentar yang menarik tentang struktur buktinya.

Mereka juga menunjukkan silsilah Blum sebagai telah membuktikan batas bawah pada kompleksitas sirkuit Boolean yang berdiri selama lebih dari 30 tahun. Ini tentu saja hanya "informasi sampingan" karena para ahli sudah serius mempelajari buktinya.

Juga di sini: https://www.quora.com/Whats-the-status-of-Norbert-Blums-claim-that-operatorname-P-neq-operatorname-NP

Mengutip Alon Amit:

(Pendapat pribadi, 14 Agustus, di kemudian hari): Saya tidak berpikir makalah ini akan tahan terhadap pengawasan. Teorema mendalam yang telah diteliti secara masif seperti halnya P ≠ NP, kemungkinan besar, akan diselesaikan dengan teknik-teknik baru yang mendalam dan berjangkauan jauh. Bukan tidak mungkin bahwa itu akan diselesaikan dengan sedikit peningkatan metode yang diketahui, yang sudah ada, tapi itu hanya sangat, sangat, sangat tidak mungkin.

Tidak mungkin benar karena alasan berikut: metode perkiraan cukup umum sehingga setiap batas bawah dapat dibuktikan menggunakannya. Ini akibat dari Razborov. Mengapa ini menjadi masalah? Karena itu berarti bahwa metode pendekatan tidak akan menjadi kemajuan utama, itu dapat mengekspresikan apa pun, daging akan berada di tempat lain. Tampaknya tidak ada daging seperti itu di koran, yang menunjukkan bahwa kemungkinan besar penulis membuat kesalahan halus, jenis kesalahan yang tersembunyi dari mata tetapi pada dasarnya adalah asumsi yang menyiratkan jawabannya. Bagi mereka yang bukan ahli teori kompleksitas: ini adalah tes penciuman yang sangat baik, ini mungkin benar seperti klaim seseorang untuk membuat roket di ruang bawah tanahnya untuk melakukan perjalanan ke bulan dalam seminggu.

Jadi di mana kesalahan kecil itu? Di blog Trevisan ada komentar oleh Lovett yang menyarankan asumsi tersembunyi apa yang ada dalam teorema 6.

$NP-c$$P$ .

$C$$f$$f$$C$$m$ gerbang .

Fungsi boolean hanya memiliki satu tabel kebenaran tetapi bukan ekspresi aljabar tunggal, tidak ada masalah yang hanya memiliki satu fungsi boolean yang menyelesaikannya.

Beberapa (mungkin semua) fungsi isomorfik (masalah tidak).

$NP=P$$m$$m$$f$$f$$f$