Pernyataan yang menyiratkan

Ini semacam pertanyaan terbuka - yang sebelumnya saya minta maaf.

Apakah ada contoh pernyataan yang (tampaknya) tidak ada hubungannya dengan kompleksitas atau mesin Turing tetapi jawabannya akan menyiratkan ?$\mathbf{P}\neq \mathbf{NP}$

Sistem bukti untuk logika proposisional disebut terikat secara polinomi , jika setiap tautologi memiliki bukti dalam sistem panjang polinomial dalam panjang .$\varphi$$\varphi$

Pernyataan "Tidak ada sistem bukti proposisional terikat secara polinomi" adalah setara dengan oleh hasil klasik Cook dan Reckhow , jadi itu menyiratkan .P ≠ N $\mathsf{NP} \neq \mathsf{co}\text-\mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Teori kompleksitas geometris (GCT) (juga [1]) belum disebutkan. ini adalah program ambisius besar untuk menghubungkan P vs NP ke geometri aljabar. misalnya sinopsis singkat dari survei Memahami Pendekatan Mulmuley-Sohoni untuk P vs. NP , Regan:

Stabilitas secara informal merupakan gagasan tidak menjadi "kacau," dan telah berkembang menjadi cabang utama geometri aljabar di bawah pengaruh penuntun DA Mumford antara lain. Ketan Mulmuley dan Milind Sohoni [MS02] mengamati bahwa banyak pertanyaan tentang kelas kompleksitas dapat diajukan kembali sebagai pertanyaan tentang sifat aksi kelompok pada vektor tertentu di ruang tertentu yang menyandikan masalah di kelas ini. Survei ini menjelaskan kerangka kerja mereka dari sudut pandang awam, dan upaya untuk mengevaluasi apakah pendekatan ini benar-benar menambah kekuatan baru untuk serangan terhadap pertanyaan P. vs. NP.

juga beberapa sinopsis di bagian "Harapan baru?" dalam Status masalah P vs NP , Fortnow (2009)

Mulmuley dan Sohoni telah mengurangi pertanyaan tentang tidak adanya algoritma waktu polinomial untuk semua masalah NP-lengkap menjadi pertanyaan tentang keberadaan algoritma waktu polinomial (dengan properti tertentu) untuk masalah tertentu. Ini seharusnya memberi kita harapan, bahkan dalam menghadapi masalah (1) - (3).

Namun demikian, Mulmuley percaya bahwa akan dibutuhkan sekitar 100 tahun untuk melaksanakan program ini, jika berhasil sama sekali.

[1] Penjelasan gaya Wikipedia tentang Geometric Complexity Theory (tcs.se)

Hasil sebagai berikut oleh Raz (Elusive Fungsi dan Hilir Bounds untuk Sirkuit Aritmatika, STOC'08) bertujuan (dan tidak langsung P ≠ N P ), tapi mungkin cukup dekat untuk OP:$VP\neq VNP$$P\neq NP$

$f:\mathbb F^n \to \mathbb F^m$$(s, r)$$Γ : \mathbb F^s → \mathbb F^m$$r$$f$$\not⊂$$Γ$

Untuk banyak pengaturan parameter , konstruksi eksplisit pemetaan polinomial yang sulit dipahami menyiratkan batas bawah yang kuat (hingga eksponensial) untuk rangkaian aritmetika umum.$n, m, s, r$

ada sedikit sisi / lebih baru dipelajari bidang kompleksitas yang disebut kompleksitas grafik yang mempelajari bagaimana grafik yang lebih besar dibangun dari grafik yang lebih kecil menggunakan operasi AND dan OR dari edge. Jukna memiliki survei yang bagus . khususnya menggunakan satuan "grafik bintang" ada teorema kunci, lihat hal. 20 komentar 1.18 (teorema secara teknis lebih kuat daripada di bawah dan sebenarnya menyiratkan ):$P \ne NP/poly$

Kita sudah mengetahui (Teorema 1.7) bahwa grafik bipartit G dari kompleksitas ada; pada kenyataannya, hampir semua grafik. Di sisi lain, Lemma Pembesaran Kuat menyiratkan bahwa bahkan batas bawah untuk konstanta kecil sewenang-wenang pada kompleksitas bintang dari grafik eksplisit dengan akan memiliki konsekuensi besar dalam kompleksitas rangkaian: grafik seperti itu akan memberikan fungsi boolean eksplisit membutuhkan rangkaian eksponensial (dalam angkaS t a r ( G ) = ( n m / log n ) S t a r ( G ) ≥ ( 2 + c ) n c > 0 n × m $n × m$$Star(G) = (nm/ \log n)$$Star(G) ≥ (2+c)n$$c > 0$$n×m$$G$f G log 2 n m G G l o g 2 n S t a r ( G ) ≥ ( 2 + c ) n c > 0 P ≠ N $m = o(n)$$f_G$$\log_2 nm$dari variabel) ukuran! (Ingatlah bahwa, untuk fungsi boolean, bahkan batas bawah super-linier tidak diketahui sejauh ini.) Secara khusus, jika grafik sedemikian rupa sehingga kedekatan simpul dalam dapat ditentukan oleh mesin Turing nondeterministic yang berjalan dalam polinomial waktu dalam panjang biner dari kode simpul, kemudian terikat lebih rendah untuk konstanta kecil yang sewenang-wenang akan menyiratkan bahwa . Dengan demikian, kompleksitas bintang dari grafik menangkap salah satu masalah paling mendasar dari ilmu komputer.$G$$G$$log_2 n$$Star(G) ≥ (2 + c)n$$c > 0$$P \ne NP$

Bagaimana dengan Philip Maymin

" Pasar efisien jika dan hanya jika P = NP " mengklaim?

Fungsi analog , dan ; , dan juga akan menarik dalam studi mereka tentang pertanyaan (?). Sementara , dan adalah masalah keputusan yang mengembalikan bit jawaban ya / tidak, , dan sebenarnya mengembalikan jawaban ( memverifikasi jawaban). Kita tahu bahwa , iff . N P F P F N P P = N P P N P 1 F P F N P F N P F P = F N P P = N $P$$NP$$FP$$FNP$$P$ $=$ $NP$$P$$NP$$1$$FP$$FNP$$FNP$$FP$ $=$ $FNP$$P$ $=$ $NP$