Haruskah kita menganggap

Banyak ahli percaya bahwa benar dan menggunakannya dalam hasil mereka. Kekhawatiran saya adalah bahwa kompleksitasnya sangat tergantung pada .$\mathsf{P} \neq \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Jadi pertanyaan saya adalah:

Selama tidak terbukti, bisakah / haruskah seseorang menganggapnya sebagai hukum alam, seperti yang ditunjukkan dalam kutipan dari Strassen? Atau haruskah kita memperlakukannya sebagai dugaan matematis yang mungkin terbukti atau tidak terbukti suatu hari nanti?$\mathsf{P}\neq\mathsf{NP}$

Mengutip:

"Bukti yang mendukung hipotesis Cook dan Valiant sangat luar biasa, dan konsekuensi dari kegagalan mereka begitu aneh, sehingga status mereka mungkin dibandingkan dengan hukum-hukum fisik dan bukan dugaan matematika biasa."

[Volker Strassen Ini puji-pujian kepada pemenang Nevanlinna Hadiah, Leslie G. Valian, pada tahun 1986]

Saya mengajukan pertanyaan ini ketika membaca posting hasil Fisika di TCS? . Hal ini mungkin menarik untuk dicatat bahwa kompleksitas komputasi memiliki beberapa kesamaan dengan (teoritis) fisik: banyak hasil kompleksitas penting telah terbukti dengan asumsi $\mathsf{P} \neq \mathsf{NP}$ , sementara dalam hasil fisik teoritis terbukti dengan mengasumsikan beberapa hukum-hukum fisika . Dalam hal ini, $\mathsf{P} \neq \mathsf{NP}$ dapat dianggap sesuatu seperti $E = mc^2$ . Kembali ke hasil Fisika di TCS? :

Mungkinkah (bagian dari) TCS menjadi cabang ilmu alam?

Klarifikasi:

(lihat jawaban Suresh di bawah)

Apakah sah untuk mengatakan bahwa dugaan dalam teori kompleksitas sama mendasarnya dengan hukum fisika dalam fisika teoretis (seperti yang dikatakan Strassen)?$\mathsf{P}\neq\mathsf{NP}$

Pernyataan Strassen perlu dimasukkan ke dalam konteks. Ini adalah alamat untuk audiens matematika pada tahun 1986, saat banyak matematikawan tidak memiliki pendapat yang tinggi tentang ilmu komputer teoritis. Pernyataan lengkapnya adalah

Bagi sebagian dari Anda, tampaknya teori-teori yang dibahas di sini bersandar pada fondasi yang lemah. Mereka tidak. Bukti yang mendukung hipotesis Cook dan Valiant begitu luar biasa, dan konsekuensi dari kegagalan mereka sangat aneh, bahwa status mereka mungkin dapat dibandingkan dengan hukum-hukum fisika dan bukan dengan dugaan matematika biasa.

Saya yakin bahwa Strassen telah melakukan percakapan dengan ahli matematika murni yang mengatakan sesuatu di sepanjang baris

"Kamu mendasarkan seluruh teori kompleksitas pada sebuah rumah kartu. Bagaimana jika P = NP? Maka semua teorema kamu akan menjadi tidak berarti. Mengapa kamu tidak hanya melakukan sedikit usaha dan membuktikan bahwa P NP, daripada terus membangun teori di atas fondasi yang lemah seperti itu. "$\neq$

Pada 2013, ketika P NP telah menjadi masalah hadiah Clay selama belasan tahun, mungkin tampaknya sulit untuk percaya bahwa setiap matematikawan benar-benar memiliki sikap seperti itu; Namun, saya pribadi dapat menjamin bahwa beberapa melakukannya.$\neq$

Strassen melanjutkan dengan mengatakan bahwa kita tidak boleh menyerah mencari bukti P NP (dengan demikian secara tidak langsung menyiratkan bahwa itu memang dugaan matematika):$\neq$

Namun demikian, bukti tradisional akan sangat menarik, dan menurut saya hipotesis Valiant mungkin lebih mudah untuk dikonfirmasikan daripada Cook ...

jadi mungkin saya akan menamakannya sebagai "hipotesis kerja" daripada "hukum fisik".

Biarkan saya akhirnya mencatat bahwa ahli matematika juga menggunakan hipotesis kerja seperti itu. Ada sejumlah besar makalah matematika yang membuktikan teorema yang pernyataannya berbunyi "Dengan asumsi hipotesis Riemann benar, maka ...".

Saya dapat melihat tiga cara terkait untuk memahami pertanyaan:

1) Bisakah kita menganggap sebagai prinsip dasar teori kompleksitas komputasi, bahkan sebelum kita dapat membuktikannya?$NP \ne P$

2) Apakah prinsip melampaui makna matematika yang sempit?$NP \ne P$

3) Apakah prinsip dapat dianggap sebagai hukum fisik.$NP \ne P$

Saya pikir ada alasan bagus untuk menjawab 'ya' atau 'ya memenuhi syarat' untuk ketiga pertanyaan ini.

Saya tidak yakin saya mengerti. Hukum fisik (dari jenis yang Anda tunjukkan) adalah ekspresi matematis dari suatu model (dalam contoh itu, relativitas) yang mengklaim dapat menangkap realitas. Hukum fisika dapat dibuktikan salah jika matematika yang mendasarinya tidak benar, tetapi bisa juga salah jika model yang mendasarinya berubah (misalnya, mekanika newton). P vs NP adalah dugaan matematis tertentu yang benar atau salah (dan mungkin bisa dibuktikan atau tidak)

Untuk menjawab pertanyaan awal Anda:

$P \ne NP$

"Asumsi Kekerasan NP ?: Tidak ada sarana fisik untuk menyelesaikan masalah NP lengkap dalam waktu polinomial".

Dia memberi ceramah yang bagus di Universitas Waterloo berjudul Computational Intractability As A Phys of Physics

$NL\neq PSPACE$$NP\neq coNP$$P\neq NP$

$\phi$$\phi$

Anda dapat melakukan banyak percobaan pada kecepatan dan kecepatan, dan Anda akan mendapatkan banyak bukti untuk memvalidasi hukum Newton. Tentu saja, Anda akan melihat beberapa hal yang sangat aneh dalam percobaan yang sangat khusus, seperti kecepatan cahaya dalam air yang bergerak, atau beberapa peristiwa astronomi. Tetapi bukti Anda yang luar biasa akan mengatakan kepada Anda: Newton benar dan hukum itu adalah yang Anda butuhkan

Tentu saja, Newton "tidak benar", dan Einstein mengejarnya.

Untuk P = NP, kita dapat melihat banyak contoh di mana tampaknya P ≠ NP. Tetapi dalam beberapa kasus tertentu, kami memiliki hal-hal aneh. Jika P ≠ NP, ada jumlah kelas yang tak terbatas di antara mereka, jadi kita harus menemukan beberapa masalah dalam NP yang tidak dalam P, tetapi tidak lengkap NP. Kami tidak tahu satu pun dari mereka, dan sebagian besar kandidat terbukti berada di P.

Apa yang Anda pikirkan tentang masalah ini tergantung pada di mana Anda ingin melihatnya. Saya tidak akan terkejut jika P = NP.