Apa masalah alami dalam teori perhitungan?

Dalam makalah Stephen Cook tentang masalah P vs NP, [1] ia menyatakan sebagai berikut:

Tesis Kelayakan: Masalah alami memiliki algoritma yang layak jika memiliki algoritma waktu polinomial.

Pertanyaan saya adalah, apa sebenarnya yang dia (atau secara umum sebenarnya, apa artinya) dengan " masalah alami "? Berbicara tentang masalah yang wajar tampaknya cukup umum, tetapi saya belum menemukan definisi. Saya sepertinya kehilangan sesuatu. Berikut adalah beberapa jawaban yang mungkin saya pikirkan:

Jawaban Kemungkinan Pertama

Cook mengatakan dalam makalahnya bahwa "alami" harus dijelaskan. Dia mengatakan, "umumnya kita tidak menganggap kelas dengan parameter sebagai alami, seperti kumpulan grafik yang dapat ditempelkan pada permukaan genus k , k > 1." [3] Sekarang, pertama-tama, ini sepertinya mengatakan apa " alami "tidak lebih dari apa adanya; tetapi jika setiap masalah adalah alami atau tidak dan ini sepenuhnya menggambarkan semua masalah yang tidak alami, maka ini akan cukup untuk mendefinisikan alami. (Tetapi kualifikasi "secara umum" menunjukkan bahwa ini bukan deskripsi yang cukup dan perlu dari masalah yang tidak wajar.)

Saya pikir "kelas dengan parameter" mengacu pada traktabilitas parameter-tetap, yang kami maksudkan adalah masalah yang memiliki kemungkinan input dibatasi sehingga kelayakan dipaksakan. Jadi kita bisa menyelesaikan masalah ransel [4] dengan algoritma polinomial-waktu jika kita memperbaiki berat ransel yang dapat dibawa (tetapi secara umum tidak ada solusi dalam waktu polinomial). Dengan ini di tangan, saya menganggap bahwa menjadi "alami" berarti masalahnya tidak dibatasi ("artifisial" dibatasi?) Dengan cara yang memaksa algoritma polinomial-waktu keluar dari masalah yang tidak dapat dipecahkan dalam waktu polinomial.

Alasan saya tidak yakin ini cara yang tepat untuk memahami gagasan Cook tentang "alami" adalah bahwa saya tidak sepenuhnya yakin apa yang kualifikasi "alami" lakukan di sini. Jika Anda menjatuhkan "alami," maka Anda mendapatkan "masalah memiliki algoritma yang layak jika memiliki algoritma waktu polinomial." Tetapi ini tampaknya masuk akal: masalah ransel tidak memiliki algoritma yang layak karena tidak memiliki algoritma waktu polinomial; knapsack-with-fix-paramater-trability memiliki algoritma yang layak karena memiliki algoritma waktu polinomial. Kedua akun tampaknya sesuai dengan gagasan tentang apa masalah dengan algoritma yang layak.

Saya kira ini mungkin panduan terbaik untuk memahami apa yang dimaksud Cook, karena Cook sebenarnya membalikkan dan mendefinisikannya. Saya juga menganggap bahwa gagasan alami ini ditangkap oleh pertanyaan StackExchange ini. [5}

Tapi ada yang lain.

Kemungkinan Jawaban Kedua

William Gasarch dalam makalahnya "Klasifikasi Masalah menjadi Kelas Kompleksitas" [6], mengatakan ia akan melakukan "diskusi literal apa yang merupakan masalah alami" [7]. Pada akhir makalah, [8] ada pertukaran dalam bentuk dialog, di mana seorang pembicara mengatakan:

"Apa yang membuat masalah itu alami? Di satu sisi, aku tidak membangun masalah dengan tujuan tidak berada di P. Jadi itu bukan masalah bodoh. Apakah itu kemudian naik ke tingkat menjadi alami?"

Jadi menurut saya apa yang dikatakan Gasarch adalah bahwa jika kita memiliki masalah yang tidak sengaja dibangun sehingga kita dapat mengatakan bahwa itu bukan dalam P, maka itu wajar. Jadi dengan sedikit interpretasi kreatif, sepertinya Gasarch mengatakan sesuatu yang setidaknya konsisten dengan Cook: di satu sisi, Gasarch mengatakan tidak dibangun dengan satu-satunya tujuan tidak berada di P membuat masalah tidak wajar; dan di sisi lain Cook mengatakan suatu masalah adalah wajar jika tidak memiliki parameter. Tetapi konsistensi belaka tidak menghasilkan definisi.

Kemungkinan Jawaban Ketiga

Pada entri Wikipedia untuk "masalah yang diajukan dengan baik" [9], definisi gagasan Jacques Hadamard tentang masalah yang diajukan dengan baik disajikan, kemudian dinyatakan bahwa masalah yang ditempatkan dengan baik "mungkin dianggap sebagai masalah 'alami' dalam hal itu ada proses fisik yang dimodelkan oleh masalah-masalah ini. " Jadi, masalah adalah wajar jika dan hanya jika itu memodelkan proses fisik?

Kualifikasi Hadamard, menurut Wikipedia, adalah (i) solusi ada, (ii) solusinya unik, dan (iii) perilaku solusi berubah terus menerus dengan kondisi awal. Ini tampaknya berbeda dari dua definisi lainnya. Perasaan saya adalah bahwa "alami" tidak digunakan dengan cara yang persis sama (terutama jika kita setuju dengan interpretasi bahwa masalah adalah wajar jika dan hanya jika itu memodelkan proses fisik), tetapi saya ingin memasukkannya karena saya bertemu dengan itu dalam penelitian saya tentang pertanyaan ini, dan ada beberapa titik kontak.

Jadi pertanyaan saya adalah: apa masalah alami? Apakah ada dari jawaban ini, atau kombinasi dari semuanya, yang benar? Apakah ada jawaban lain yang saya lewatkan? Terima kasih.

1. "The Statement of the Problem," 2006, diposting secara online di the Clay Mathematics; judul: "Masalah P vs NP", http://www.claymath.org/sites/default/files/pvsnp.pdf
2. hal. 3
3. hal. 4
4. https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem
5. Masalah alam paling sulit diketahui dalam P? Saya menganggap bahwa masalah alami mengikuti uraian ini tetapi tidak membatasi k untuk menjadi yang terbesar.
6. https://www.cs.umd.edu/~gasarch/papers/classcomp.pdf
7. hal. 2.
8. hal. 47-8, bagian 25
9. https://en.wikipedia.org/wiki/Well-posed_problem

Untuk lebih jelasnya, itu tidak dimaksudkan untuk diformalkan. Ini bukan teorema, ini adalah pengamatan tentang dunia - tidak apa-apa jika "alami" subjektif di sini. Sebagai analogi, jika seseorang mengatakan "diferensiasi adalah mekanika sedangkan integrasi adalah seni", mereka tidak mengundang Anda untuk meresmikan "mekanika" dan "seni" dan membuktikan pernyataan itu, mereka mencoba menyampaikan perspektif umum. Jadi, Anda mungkin sedikit kehilangan hutan untuk pepohonan di sini.

Apa maksud penulisnya?

Mari ikuti saran Anda dan letakkan kata "natural":

Tesis Kelayakan (draft pertama): Suatu masalah memiliki algoritma yang layak jika memiliki algoritma waktu polinomial.

$n^{1000}$$n^{1000}$

Jadi penulis merasa tesis ini masih cukup akurat mengenai masalah yang sebenarnya ingin kita selesaikan di dunia nyata dan masalah lain yang dihadapi "secara alami" dalam perjalanan kehidupan teori-non-kompleksitas. Jadi dia berpikir, mari kita sebut masalah itu "alami" dan merevisi tesis kelayakan.

Apa itu dan tidak alami

Yang pasti, masalah yang muncul secara umum dalam praktik akan dianggap alami: jalur terpendek, pengurutan, edit jarak, pencarian akar, salesman keliling, ransel.

Yang pasti, masalah yang dipikirkan dan didefinisikan secara khusus untuk membuktikan hasil kompleksitas, dan referensi kelas tertentu, tidak alami. Misalnya, "dapatkah string ini dihasilkan oleh mesin Turing pada status k dalam waktu n".

Beberapa hal kurang jelas, seperti mungkin pemrograman linier, tetapi saya tidak akan terlalu khawatir tentang hal itu. Pelajari banyak masalah algoritma dan kompleksitas dan lihat apakah Anda setuju dengan gagasan umum, atau jika Anda menemukan contoh yang menurut Anda bertentangan dengannya.

(Bagaimanapun saya pikir rute "masalah yang diajukan dengan baik" tentu saja salah, seperti yang Anda duga.)

[catatan kaki] Saya tidak bermaksud menghalangi Anda untuk mencoba memformalkannya, hanya dari berpikir bahwa Anda memang seharusnya demikian.

Ini secara kasar bermuara pada apakah definisi masalah bisa melingkar:

• Masalah buatan adalah salah satu yang dibangun untuk memenuhi kriteria kelasnya.

• Masalah alami tidak bergantung pada metode konstruksinya untuk memenuhi kriteria kelas.

Konstruksi Ladner dikenal sebagai perantara-NP , asalkan NPI ada.

$P \subsetneq NP$

Perhatian: Semoga berhasil mencoba membuktikan kandidat semacam itu; Ini mungkin tampak seperti pendekatan yang dapat diakses tetapi secara alami telah mengembangkan beberapa hambatan pada bukti .