Masalah yang dapat digunakan untuk menunjukkan hasil kekerasan waktu polinomial

Ketika merancang suatu algoritma untuk masalah baru, jika saya tidak dapat menemukan algoritma waktu polinomial setelah beberapa saat, saya mungkin mencoba membuktikannya sebagai NP-hard. Jika saya berhasil, saya sudah menjelaskan mengapa saya tidak dapat menemukan algoritma waktu polinomial. Bukannya saya tahu pasti bahwa P! = NP, hanya saja ini yang terbaik yang bisa dilakukan dengan pengetahuan saat ini, dan memang konsensusnya adalah bahwa P! = NP.

Demikian pula, katakan saya telah menemukan solusi polinomial-waktu untuk beberapa masalah, tetapi waktu yang berjalan adalah . Setelah banyak upaya, saya tidak membuat kemajuan dalam meningkatkan ini. Jadi, sebagai gantinya, saya mungkin mencoba membuktikan bahwa ini adalah 3SUM-hard. Ini biasanya keadaan yang memuaskan, bukan karena keyakinan tertinggi saya bahwa 3SUM memang membutuhkan waktu , tetapi karena ini adalah keadaan seni saat ini, dan banyak orang pintar telah mencoba untuk meningkatkan itu, dan telah gagal. Jadi bukan salah saya bahwa itu yang terbaik yang bisa saya lakukan.Θ ( n 2$O(n^2)$$\Theta(n^2)$

Dalam kasus seperti itu, yang terbaik yang bisa kita lakukan adalah hasil kekerasan, sebagai pengganti batas bawah yang sebenarnya, karena kita tidak memiliki batas bawah super-linear untuk Mesin Turing untuk masalah dalam NP.

Apakah ada serangkaian masalah yang seragam yang dapat digunakan untuk semua waktu menjalankan polinomial? Sebagai contoh, jika saya ingin membuktikan bahwa tidak mungkin beberapa masalah memiliki algoritma yang lebih baik daripada , apakah ada beberapa masalah X sehingga saya dapat menunjukkannya X-keras dan membiarkannya begitu saja?$O(n^7)$

Pembaruan : Pertanyaan ini awalnya menanyakan keluarga masalah. Karena tidak ada banyak keluarga masalah, dan pertanyaan ini telah menerima contoh luar biasa dari masalah sulit individu, saya melonggarkan pertanyaan untuk masalah apa pun yang dapat digunakan untuk hasil kekerasan waktu polinomial. Saya juga menambahkan hadiah untuk pertanyaan ini untuk mendorong lebih banyak jawaban.

Ya, algoritma yang paling dikenal untuk -SUM berjalan dalam waktu , jadi sangat mungkin bahwa Anda dapat memperdebatkan beberapa masalah sulit, karena jika itu dalam maka Anda bisa menyelesaikan -SUM lebih cepat.O ( n ⌈ k / 2 ⌉ ) n 7 n 6.99$k$$O(n^{\lceil k/2 \rceil})$$n^7$$n^{6.99}$$14$

Perhatikan bahwa masalah -SUM menjadi "lebih mudah" karena bertambah: mengingat algoritma yang ditingkatkan untuk -SUM, cukup mudah untuk mendapatkan algoritma yang ditingkatkan untuk -SUM: ambil semua pasangan dari angka di diberi contoh -SUM, mengganti setiap pasangan dengan jumlah keduanya, dan mencari jumlah dari jumlah yang sama dengan . Kemudian, sebuah algoritma untuk -SUM menyiratkan algoritma untuk -SUM. Dengan kata lain, batas bawah yang ketat untukk k 2 k O ( n 2 ) n 2 k k 0 O ( n k / 2 - ε ) k O ( n k - 2 ε ) 2 k 2 k $k$$k$$k$$2k$$O(n^2)$$n$$2k$$k$$0$$O(n^{k/2-\varepsilon})$$k$$O(n^{k-2\varepsilon})$$2k$$2k$-SUM adalah asumsi yang lebih kuat daripada batas bawah ketat untuk -SUM.$k$

Kandidat lain untuk masalah yang sulit adalah -Clique. Lihat saya -Clique jawaban untuk lebih lanjut tentang itu . Jika Anda dapat menunjukkan (misalnya) bahwa algoritma yang lebih baik untuk masalah Anda menyiratkan algoritma untuk -clique, maka terobosan super akan diperlukan untuk meningkatkan algoritma Anda. Kompleksitas parameter memberi banyak contoh masalah lain seperti ini: -Clique sulit untuk kelas , dan -SUM sulit untuk .O ( log n ) O ( n 2 ) 3 k W \ [ 1 \] k W \ [ 2 $k$$O(\log n)$$O(n^2)$$3$$k$$W\[1\]$$k$$W\[2\]$

Biarkan saya memperingatkan Anda bahwa meskipun masalah seperti ini sangat mudah untuk dikerjakan, masalah seperti -SUM tidak termasuk yang "paling sulit" dalam , misalnya, sangat tidak mungkin bahwa setiap masalah dalam sebenarnya bisa linear-waktu dikurangi menjadi -SUM. Ini karena -SUM dapat diselesaikan dengan bit nondeterminisme dalam waktu linier, jadi jika semuanya dalam waktu kuadratik dapat dikurangi menjadi -SUM, maka dan hasil konsekuensi fantastis lainnya. Lebih tentang hal ini dapat ditemukan dalam artikel "Bagaimana keras adalah -Hard masalah?"T I M E [ n 2 ] T I M E [ n 2 ] 3 3 O ( log n ) 3 P ≠ N P n 2 n $3$$TIME[n^2]$$TIME[n^2]$$3$$3$$O(\log n)$$3$$P \neq NP$$n^2$(Pada titik tertentu, "3SUM-hard" disebut " -hard"; artikel SIGACT ini dengan tepat mengeluhkan nama itu.)$n^2$

Masalah All-Pairs Shortest Paths (APSP) diyakini membutuhkan waktu waktu. Mengurangi dari itu adalah cara yang bagus untuk berpendapat bahwa perbaikan berdasarkan Fast Matrix Multiplication (FMM) tidak mungkin.$\Omega^\star(n^3)$

Dipercaya bahwa algoritma terbaik untuk masalah degenerasi afin dalam ruang dimensi dijalankan dalam waktu . Masalahnya adalah sebagai berikut: Diberikan poin dalam ruang dimensional dengan koordinat bilangan bulat, apakah ada poin terletak pada hyperplane bersama?O ( n d ) n d d + $d$$O(n^d)$$n$$d$$d+1$

Masalah degenerasi afin adalah -SUM keras. Jika kita pasang batas bawah dugaan untuk -SUM, kita memperoleh batas bawah . Dugaan untuk kompleksitas masalah degenerasi afin jauh lebih kuat untuk .k Ω ( n ⌊ d / 2 ⌋ + 1 ) d ≥ $(d+1)$$k$$\Omega(n^{\lfloor d/2 \rfloor +1})$$d \geq 3$

J. Erickson, S. Har-Peled, dan Mount DM, On the Least Median Square Problem, Diskrit dan Geometri Komputasi, 36, 593-607, 2006. http://www.cs.umd.edu/~mount/Papers /dcg06-lms.pdf

J. Erickson dan R. Seidel. Batas bawah yang lebih baik dalam mendeteksi degenerasi bola dan bola. Komputasi Terpisah. Geom., 13: 41–57, 1995. http://compgeom.cs.uiuc.edu/~jeffe/pubs/degen.html

J. Erickson. Batas bawah baru untuk masalah hull cembung dalam dimensi aneh. SIAM J. Comput., 28: 1198–1214, 1999. http://compgeom.cs.uiuc.edu/~jeffe/pubs/convex.html

Masalah Hopcroft diperkirakan membutuhkan waktu : Diberikan satu set poin dan satu set garis dalam pesawat, apakah ada titik yang terletak pada garis apa pun?n $\Theta(n^{4/3})$$n$$n$