Kompleksitas waktu deterministik yang diketahui paling baik untuk masalah alami dalam NP

Jawaban ini untuk masalah utama yang belum terpecahkan dalam ilmu komputer teoritis? pertanyaan menyatakan bahwa itu terbuka jika masalah tertentu dalam NP membutuhkan waktu .$\Omega(n^2)$

Melihat komentar di bawah jawaban membuat saya bertanya-tanya:

Selain dari padding dan trik serupa, apa kompleksitas waktu paling dikenal yang terikat lebih rendah pada mesin RAM deterministik (atau mesin Turing deterministik multi-tape) untuk masalah yang menarik dalam NP (yang dinyatakan secara alami)?

Apakah ada masalah alami dalam NP yang diketahui tidak dapat diselesaikan dalam waktu deterministik kuadrat pada model mesin yang masuk akal?

Pada dasarnya, apa yang saya cari adalah contoh yang mengesampingkan klaim berikut:

setiap alami masalah NP dapat diselesaikan dalam waktu.$O(n^2)$

Apakah kita tahu masalah NP yang mirip dengan yang ada dalam makalah Karp tahun 1972 atau Garey dan Johnson 1979 yang membutuhkan waktu deterministik? Atau mungkinkah sepengetahuan kami bahwa semua masalah NP alami yang menarik dapat diselesaikan dalam waktu deterministik O ( n 2 ) ?$\Omega(n^2)$$O(n^2)$

Edit

Klarifikasi untuk menghilangkan kebingungan yang timbul dari ketidaksesuaian antara batas bawah dan bukan batas atas : Saya mencari masalah yang kita tahu tidak bisa kita selesaikan di . Jika masalah memenuhi persyaratan kuat bahwa Ω ( n 2 ) atau ω ( n 2 ) waktu yang diperlukan (untuk semua input yang cukup besar) maka lebih baik, tapi jauh akan sering melakukan.$o(n^2)$$\Omega(n^2)$$\omega(n^2)$

Adachi, Iwata, dan Kasai dalam makalah JACM 1984 menunjukkan dengan reduksi bahwa permainan Cat dan -Mice memiliki batas waktu n Ω ( k ) yang lebih rendah. Masalahnya adalah dalam P untuk setiap k . Masalahnya dimainkan pada grafik yang diarahkan. Bergerak terdiri dari kucing dan kemudian salah satu k langkah bolak tikus. Tikus-tikus menang jika mereka bisa mendarat pada simpul keju yang ditentukan sebelum kucing mendarat di atasnya. Pertanyaannya adalah apakah kucing itu menang secara paksa. Ini sebenarnya masalah lengkap sehingga batas bawah benar-benar didasarkan pada diagonalisasi yang memberikan hierarki waktu.$k$$n^{\Omega(k)}$$k$$k$

Grandjean menunjukkan bahwa batas bawah Pippenger, Paul, Szemeredi, dan Trotter berlaku untuk penyandian SAT, meskipun hasil Santhanam dapat mengikutinya.

Selain batas waktu tradeoff ruang-waktu untuk SAT yang disebutkan dalam komentar lain, ada badan kerja pada program percabangan batas bawah yang menyiratkan tradeoff ruang-waktu untuk mesin Turing. Untuk masalah seperti FFT, pengurutan atau penghitungan fungsi hash universal, ada tradeoff kuadratik batas bawah Borodin-Cook, Abrahamson, Mansour-Nisan-Tiwari tetapi ini untuk fungsi dengan banyak output. Untuk masalah keputusan dalam P, ada tradeoff batas waktu dan batas bawah yang berlaku untuk batas waktu yang tetapi ini lebih lemah daripada yang diketahui untuk SAT.$O(n \log n)$

Hasil klasik yang saya tahu adalah karena Paul, Pippenger, Szemeredi dan Trotter (1983) dan memisahkan deterministik dari waktu linier non-deterministik.

Kemudian, ada hasil yang lebih baru oleh Fortnow, Lipton, van Melkebeek dan Viglas (2004) yang telah disebutkan. Keunikan dari hasil ini adalah bahwa itu adalah hasil tradeoff ruang-waktu, ruang pembatas serta waktu.

Namun, saya juga mengetahui hasil karena Santhanam (2001) yang membuktikan batas bawah . Hasil ini sedikit lebih kuat untuk batasan waktu daripada yang di atas, tetapi tidak memberikan jaminan ruang.$\omega (n \sqrt{ \log ^{*} n} )$

Mengingat di atas serta pengetahuan saya tentang lapangan, saya akan mengatakan bahwa membuktikan bahwa ada masalah -Lengkap yang tidak dapat diselesaikan dalam O ( n 2$\mathbb{NP}$$O(n^{2})$ waktu deterministik akan cukup langkah besar. Sejauh yang saya tahu, hasil seperti itu dianggap sangat tidak trivial dan kemungkinan membutuhkan teknik batas bawah yang baru.

Catatan: Kata-kata saya tentang masalah pada paragraf terakhir berbeda dari pada pertanyaan Anda. Saya bisa menjadi rewel (dan mungkin tidak banyak membantu) dan memberi tahu Anda bahwa secara sepele ada jumlah masalah yang tak terbatas dalam dan dengan demikian dalam N P yang tidak dapat diselesaikan dalam O ( n 2 ) waktu deterministik, oleh waktu deterministik teorema hierarki.$\mathbb{P}$$\mathbb{NP}$$O(n^{2})$

Sunting: Setelah berpikir lebih lanjut, inilah cara Anda dapat menemukan masalah dalam yang sesuai dengan kebutuhan Anda:$\mathbb{NP}$

1. $DTIME ( f(n) )$$f(n) = \Omega ( n^{2} \log n)$$\omega( n^{2} )$
2. $NTIME ( f(n) )$$f(n) = \omega ( n^{2} )$
3. $SPACE ( f(n) )$ , where $f(n) = \omega ( n^{2} / \log n)$. This is justified by the TIME-SPACE separation. I believe that

The above lower bounds should hold for the bit complexity of the problem.

Once again, if you restrict your attention to $\mathbb{NP}$-complete problems, I am not aware of such lower bounds.

Perhaps a fairly natural example comes from time-bounded Kolmogorov complexity:

For any fixed $k$, and fixed function $f(n) \leq n$ you can ask: "Given a binary string $x$, does a Turing machine $M$ exist such that $|M| < f(|x|)$ and $M$ produces $x$ in less than $|x|^k$ steps?"

This is just reasking the same question of P=NP in the a different way, if you can prove that its unsolvable in quadratic time or find an absolute lower bound, you would be proving P!=NP