Implikasi dari unprovability dari

22

Saya membaca " Apakah P Versus NP Secara Independen? " Tetapi saya bingung.

Dipercaya secara luas dalam teori kompleksitas bahwa . Pertanyaan saya adalah bagaimana jika ini tidak dapat dibuktikan (katakanlah di ). (Mari kita asumsikan bahwa kita hanya mengetahui bahwa independen dari tetapi tidak ada informasi lebih lanjut tentang bagaimana ini terbukti.) $\mathsf{P} \neq \mathsf{NP}$ $ZFC$ $\mathsf{P} \neq \mathsf{NP}$ $ZFC$

Apa yang akan menjadi implikasi dari pernyataan ini? Lebih spesifik,

kekerasan

Dengan asumsi bahwa menangkap algoritma yang efisien ( tesis Cobham-Edmonds ) dan , kami membuktikan hasil menyiratkan bahwa mereka adalah di luar jangkauan algoritma efisien kami saat ini. Jika kita membuktikan pemisahan, berarti bahwa tidak ada algoritma waktu polinomial. Tetapi apa artinya hasil jika pemisahan tidak dapat dibuktikan? Apa yang akan terjadi pada hasil ini? $\mathsf{P}$ $\mathsf{P} \neq \mathsf{NP}$ $\mathsf{NP\text{-}hardness }$ $\mathsf{NP\text{-}hardness}$ $\mathsf{NP\text{-}hardness }$

algoritma yang efisien

Apakah ketidakterpisahan pemisahan berarti kita perlu mengubah definisi kita tentang algoritma yang efisien?

cc.complexity-theory np-hardness big-picture proofs p-vs-np karthik
sumber

13

Hal pertama yang perlu Anda tanyakan adalah: terlepas dari apa secara formal? Dalam logika matematika, ada banyak set aksioma yang telah dipertimbangkan. Yang default adalah ZFC, atau teori set Zermelo-Fraenkel dengan Aksioma Pilihan. Apa artinya menjadi independen dari ZFC adalah bahwa P = NP atau P! = NP tidak dapat dibuktikan dari aksioma ini.

Peter Shor

2

Jika Anda ingin tahu seperti apa bukti pernyataan dari bentuk "apakah X atau tidak independen dari sistem aksiomatik Y", mengapa Anda tidak membaca beberapa contoh saja? Kemandirian Aksioma Pilihan dari teori himpunan Zermelo-Fraenkel adalah contoh yang terkenal. Saya memilih untuk menutup sebagai bukan pertanyaan nyata karena kesalahan, tetapi saya bermaksud untuk memilih untuk menutup sebagai topik.

Tsuyoshi Ito

15

Apakah Anda membaca makalah Scott Aaronson yang sangat bagus dan tersedia secara bebas; "Apakah P vs. NP Secara Independen?" ( scottaaronson.com/papers/pnp.pdf )

Marzio De Biasi

2

Pertanyaan "jika X terbukti independen dari ZFC, dan kami memiliki beberapa teorema dari bentuk X

Y, apa yang terjadi pada teorema ini?" tampaknya diajukan dengan baik, dan merupakan pertanyaan yang saya yakini ditanyakan OP. Jawabannya tampaknya: dalam beberapa sistem aksioma, seperti ZFC + X, kita kemudian memiliki holding Y, sementara di ZFC +

X kita tidak memiliki informasi tentang Y. Dengan demikian, teorema bersyarat ini masih memiliki beberapa nilai. Bahkan, mereka akan memiliki nilai lebih dalam situasi ini daripada jika

X terbukti menjadi teorema.

\to

$\rightarrow$

\neg

$\lnot$

\neg

$\lnot$

András Salamon

2

The ZFC unprovability dari P vs NP mungkin akan memiliki lebih banyak implikasi untuk Teori Set daripada Teori Kompleksitas.

David Harris

18

Pertanyaan Anda mungkin lebih baik diungkapkan, "Bagaimana teori kompleksitas akan dipengaruhi oleh penemuan bukti bahwa P = NP secara formal independen dari beberapa sistem aksiomatik yang kuat?"

Agak sulit untuk menjawab pertanyaan ini secara abstrak, yaitu, dengan tidak adanya melihat rincian buktinya. Seperti yang disebutkan Aaronson dalam makalahnya, membuktikan independensi P = NP akan membutuhkan ide-ide baru yang radikal, bukan hanya tentang teori kompleksitas, tetapi juga tentang bagaimana membuktikan pernyataan independensi. Bagaimana kita dapat memprediksi konsekuensi dari terobosan radikal yang bentuknya saat ini kita bahkan tidak bisa menebaknya?

Meski begitu, ada beberapa pengamatan yang bisa kita lakukan. Setelah bukti kemandirian hipotesis kontinum dari ZFC (dan kemudian dari ZFC + kardinal besar), sejumlah besar orang datang ke sudut pandang bahwa hipotesis kontinum tidak benar atau salah . Kita dapat bertanya apakah orang juga akan sampai pada kesimpulan bahwa P = NP adalah "tidak benar atau salah" setelah bukti independensi (demi argumen, mari kita misalkan P = NP terbukti independen dari ZFC + besar aksioma kardinal). Dugaan saya tidak. Aaronson pada dasarnya mengatakan bahwa dia tidak akan melakukannya. Teorema ketidaklengkapan ke-2 Goedel tidak membuat siapa pun yang saya tahu berpendapat bahwa "ZFC konsisten" tidak benar atau salah. $\ne$

Kita juga dapat bertanya apakah orang akan menafsirkan keadaan ini dengan mengatakan bahwa ada sesuatu yang "salah" dengan definisi P dan NP kita. Mungkin kita kemudian harus mengulang dasar-dasar teori kompleksitas dengan definisi baru yang lebih mudah dikerjakan? Pada titik ini saya pikir kita berada di dunia spekulasi liar dan tidak berbuah, di mana kita mencoba untuk menyeberangi jembatan yang belum kita dapatkan dan mencoba untuk memperbaiki hal-hal yang belum rusak. Selain itu, bahkan tidak jelas apa pun akan terjadi"rusak" dalam skenario ini. Para teoris set sangat senang dengan asumsi aksioma kardinal besar yang mereka rasa nyaman. Demikian pula, para ahli teori kompleksitas mungkin juga, dalam dunia hipotetis masa depan ini, sangat senang mengasumsikan setiap aksioma pemisahan yang mereka yakini benar, meskipun mereka terbukti tidak dapat dibuktikan.

Singkatnya, tidak banyak yang mengikuti secara logis dari bukti independensi P = NP. Wajah teori kompleksitas mungkin berubah secara radikal mengingat terobosan fantastis seperti itu, tetapi kita hanya harus menunggu dan melihat seperti apa terobosan itu.

Timothy Chow
sumber

3

E

$E$

E

$E$

E

$E$

E

$E$

E

$E$

4

@ vz: Saya pikir Anda benar-benar kehilangan intinya. Pertanyaannya bukanlah apakah pernyataan tertentu tidak dapat diputuskan , tetapi apakah itu tidak benar atau salah . Kedua konsep itu sepenuhnya berbeda. Apakah Anda akan mengatakan, misalnya, bahwa ZFC tidak konsisten atau tidak konsisten? Semua orang (yang lain) yang saya tahu percaya bahwa ZFC konsisten, atau tidak, meskipun kita mungkin tidak memiliki cara untuk menentukan mana yang menjadi masalahnya.

Timothy Chow

3

"Ini kedengarannya seperti agama bagi saya dan bukan matematika" - Selamat datang di metamathematics. Mungkin cara yang kurang disukai untuk mengatakan "X tidak benar atau salah" adalah bahwa kita tidak memiliki alasan apriori untuk lebih memilih sistem aksiomatik di mana X benar daripada sistem aksiomatik di mana X salah. Kami memiliki (hampir) model standar aritmatika yang disepakati secara universal; sebagai konvensi sosial, kami menerima pernyataan aritmatika yang menyatakan bahwa model itu benar-benar benar. Hal yang sama tidak dapat dikatakan untuk teori himpunan.

Jeffε

2

Lihat juga consc.net/notes/continuum.html dan mathoverflow.net/questions/14338/… - Setiap campuran matematikawan formalisme, platonisme, dan intuitionisme pada dasarnya adalah keyakinan agama.

Jeffε

2

@ vzn: Anda masih merindukan intinya. Bahkan jika kami memberi Anda keyakinan agama pribadi Anda, semua yang Anda katakan adalah bahwa Anda tidak akan bergabung dengan Aaronson dan seluruh dunia dalam mendeklarasikan kalimat aritmetika sebagai benar atau salah. Kita semua setuju bahwa tidak ada cara untuk mengetahui dari bentuk pernyataan apakah itu tidak dapat diputuskan , tetapi itu bukan klaim. Klaimnya adalah bahwa hampir semua orang kecuali Anda memang memiliki intuisi kuat bahwa pernyataan aritmetika benar atau salah . Hanya karena Anda tidak berbagi keyakinan itu tidak berarti bahwa orang lain tidak memilikinya.

Timothy Chow

11

Ini adalah pertanyaan yang valid, meskipun mungkin sedikit sayangnya diutarakan. Jawaban terbaik yang bisa saya berikan adalah referensi ini:

Scott Aaronson: Apakah P versus NP secara independen independen . Buletin Asosiasi Eropa untuk Ilmu Komputer Teoritis, 2003, vol. 81, halaman 109-136.

Abstrak: Ini adalah survei tentang pertanyaan judul, ditulis untuk orang-orang yang (seperti penulis) melihat logika sebagai melarang, esoteris, dan jauh dari masalah yang biasa mereka alami. Dimulai dengan kursus kilat tentang teori himpunan Zermelo Fraenkel, ia membahas independensi oracle; bukti alami; hasil kemerdekaan Razborov, Raz, DeMillo-Lipton, Sazanov, dan lainnya; dan hambatan untuk membuktikan P vs NP independen dari teori logis yang kuat. Itu berakhir dengan beberapa pemikiran filosofis tentang kapan seseorang harus mengharapkan pertanyaan matematis untuk mendapatkan jawaban pasti.

Andrej Bauer
sumber

2

Eh, saya benar-benar merindukan fakta bahwa makalah Aaronson sudah disebutkan dalam komentar. Permintaan maaf saya.

Andrej Bauer

7

$[ZFC][1]$ . Ini hanya berarti bahwa teori tersebut tidak dapat membuktikan pernyataan maupun negasinya. Itu tidak berarti bahwa pernyataan itu tidak memiliki nilai kebenaran, itu tidak berarti bahwa kita tidak dapat mengetahui nilai kebenaran dari pernyataan itu, kita mungkin dapat menambahkan aksioma wajar yang baru yang akan membuat teori cukup kuat untuk dapat untuk membuktikan pernyataan atau negasinya. Pada akhirnya, provabilitas dalam teori adalah konsep abstrak formal. Ini terkait dengan pengalaman dunia nyata kita hanya sebagai model.

$\mathsf{P}$

$\Sigma_1$ $\Pi_1$ Topologi via Logika ", 1996.)

$\mathsf{P} \neq \mathsf{NP}$ $\Sigma_2$ , dan cari posting di milis FOM .

Kaveh
sumber

4

Sebagaimana dibuktikan dalam tulisan ini:

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0699.revised.pdf

Jika P! = NP dapat ditunjukkan tidak bergantung pada Aritmatika Peano, maka NP memiliki batas atas waktu deterministik sangat polinomial yang sangat dekat. Khususnya, dalam kasus seperti itu, ada algoritma DTIME (n ^ 1og * (n)) yang menghitung SAT dengan benar pada banyak interval panjang input yang tak terhingga.

Avi Tal
sumber

0

Hanya beberapa pemikiran bertele-tele tentang ini. Jangan ragu untuk mengkritik.

Misalkan Q = [tidak bisa membuktikan (P = NP) dan tidak bisa membuktikan (P / = NP)]. Misalkan Q untuk suatu kontradiksi. Saya juga akan menganggap bahwa semua penemuan yang diketahui tentang P vs NP masih layak. Secara khusus, semua masalah NP setara dalam arti bahwa jika Anda dapat menyelesaikan salah satu dari mereka dalam waktu polinomial, Anda dapat menyelesaikan semua yang lain dalam waktu polinomial. Jadi biarkan W menjadi masalah lengkap NP; W sama mewakili semua masalah dalam NP. Karena Q, seseorang tidak dapat memperoleh algotithm A untuk menyelesaikan W dalam waktu polinomial. Kalau tidak, kita memiliki bukti bahwa P = NP, yang bertentangan dengan Q (1) (*). Perhatikan bahwa semua algoritma dapat dihitung berdasarkan definisi. Jadi mengatakan bahwa A tidak dapat eksis menyiratkan bahwa tidak ada cara untuk menghitung W dalam waktu polinomial. Tapi ini bertentangan dengan Q (2). Kita dibiarkan menolak (1) atau menolak (2). Kedua kasus tersebut mengarah pada sebuah kondradiksi. Jadi Q adalah kontradiksi,

(*) Anda mungkin berkata, "Aha! A mungkin ada, tetapi kami tidak dapat menemukannya". Nah, jika A ada, kita dapat menghitung melalui semua program untuk menemukan A dengan menyebutkan dari program yang lebih kecil ke program yang lebih besar, dimulai dengan program kosong. A harus terbatas karena ini adalah algoritma, jadi jika A ada, maka program enumerasi untuk menemukannya harus diakhiri.

Thomas Eding
sumber

1

@ Viktor: Poin bagus. Saya membayangkan bahwa jika A ada, maka seseorang dapat dengan mudah menganalisis setiap program yang disebutkan untuk melihat apakah memang memecahkan masalah NP lengkap dalam waktu polinomial. Saya percaya bahwa karena seseorang bekerja dengan set instruksi yang terbatas (diberikan oleh beberapa komputer universal) maka A dapat diidentifikasi. Tapi saya bukan ahli.

Thomas Eding

1

Masalahnya adalah jika Q benar, maka kita akan jatuh dalam kasus di mana tidak ada orang, tidak peduli seberapa cerdasnya, dapat membuktikan bahwa algoritma tertentu X yang dihasilkan oleh enumerator memecahkan P = NP, bahkan jika itu benar. Yaitu dalam kasus ini, sebuah algoritma untuk menentukan apakah P = NP ada dan dapat ditemukan, tetapi tidak mungkin untuk membuktikan kebenarannya secara analitis. Selanjutnya pernyataan seperti "apakah algoritma X memecahkan masalah P = NP?" Kedengarannya sangat tidak dapat dipastikan.

Victor Stafusa

1

Juga ... Jika A ada, maka misalkan N menjadi ukuran A. Misalkan T adalah himpunan semua program ukuran <= N. Satu dapat secara bersamaan menjalankan W pada semua A 'di T. Karena setiap A' berakhir, jalankan output O melalui program yang memeriksa untuk melihat apakah O memecahkan W. (Perhatikan bahwa apa yang disebut 'solusi' untuk masalah NP lengkap dapat diverifikasi dalam waktu polinomial.) Jika O adalah jawaban yang benar, matikan semua komputer lain dan mengembalikan O. Ingatlah bahwa tidak setiap A harus diakhiri karena A adalah salah satunya dan akan menghasilkan O yang benar dalam waktu polinomial. Jadi seseorang tidak perlu membuktikan bahwa A memecahkan P = NP. N ada menurut definisi.

Thomas Eding

1

Di bagian (*) Anda: "A harus terbatas karena ini adalah algoritma, jadi jika A ada, maka program enumerasi untuk menemukannya harus diakhiri.". Ini berarti bahwa enumerator harus entah bagaimana dapat menentukan apakah program yang baru saja dihasilkan menyelesaikan masalah NP-lengkap dalam waktu polinomial, yang tentunya tidak dapat dipastikan (bahkan lebih karena kita mengasumsikan Q di sini), dan dengan demikian enumerator tidak akan pernah berhenti .

Victor Stafusa

3

"P = NP tidak tergantung pada ZFC" tidak sama dengan "kami tidak dapat menemukan algoritma untuk menyelesaikan masalah dalam NP dalam waktu polinomial deterministik", seperti yang ditunjukkan Victor. Definisi yang tepat dari kelas-kelas ini agak penting ketika berhadapan dengan gagasan seperti independensi sehubungan dengan teori.

András Salamon

Implikasi dari unprovability dari

kekerasan

algoritma yang efisien

Jawaban: