Apakah ada masalah nontrivial dalam teori algoritma serial dengan batas bawah polinomial nontrivial

Dalam teori algoritma terdistribusi, ada masalah dengan batas bawah, seperti $\Omega(n^2)$, itu "besar" (maksud saya, lebih besar dari $\Omega(n\log n)$), dan nontrivial. Saya bertanya-tanya apakah ada masalah dengan ikatan yang serupa dalam teori algoritma serial, maksud saya urutan jauh lebih besar dari .$\Omega(n\log n)$

Dengan sepele, maksud saya "diperoleh hanya dengan mempertimbangkan bahwa kita harus membaca seluruh input" dan juga.

Ada masalah dengan teorema hierarki waktu. Ambil saja masalah yang lengkap untuk kelas kompleksitas besar. Misalnya, ambil masalah yang lengkap$\mathsf{ExpTime}$. Masalah seperti itu akan terjadi$\Omega(n^c)$ untuk semua $c\in\mathbb{N}$.

Namun perhatikan juga untuk masalah di $\mathsf{NP}$, tidak ada batas bawah waktu yang kuat dalam model TM multi-tape dan keberadaan algoritma waktu linier untuk SAT konsisten dengan pengetahuan terkini. (Dalam model TM single-tape tidak sulit untuk menunjukkan bahwa banyak masalah seperti palindrom membutuhkan$\Omega(n^2)$ waktu tetapi batas bawah seperti itu pada dasarnya bergantung pada keterangan model single-tape TM.)

Beberapa masalah sederhana yang memiliki batas lebih rendah lebih besar dari ukuran inputnya, adalah algoritma yang memiliki ukuran output lebih besar dari ukuran inputnya.

Beberapa contoh:

• Masalah daftar semua solusi untuk 3-SAT, atau sama halnya, masalah daftar semua siklus Hamilton . Masalah-masalah ini keduanya memiliki sejumlah solusi eksponensial dalam kasus terburuk. Dengan demikian mereka memiliki batas bawah$\Omega (c^n),c>1$. Namun yang menarik, masalah 3-SAT itu sendiri tidak diketahui super linier (lebih dari$\Omega (n)$) terikat! Ini berarti kita tidak tahu apakah ini lebih sulit daripada linear!
• Anda bahkan dapat membuat algoritma baru seperti ini: "melengkapi grafik" yang diberikan $G = V,E$dimana $E=\varnothing$, dan $n=|V|$, algoritma akan menampilkan grafik $G' = V,E'$dimana $E'=\left\{u,v|u\neq v\space\wedge\space u,v\in V \right\}$.

Selain itu, Anda mungkin dapat menyusun masalah yang ada $\Omega (n^2)$Output -sized, dengan masalah yang dibutuhkan $\Omega (n^2)$ sebagai input, dan output $\Omega (n)$ atau bahkan $\Omega (1)$-ukuran output (misalnya, sesuatu yang menghitung jumlah output) untuk mendapatkan masalah yang dibutuhkan $\Omega(n)$-ukuran input, dan output $\Omega (n)$-ukuran output, namun memiliki waktu berjalan lebih dari $\Omega (n)$. Namun mungkin sangat sulit untuk dibuktikan (bahwa tidak ada jalan pintas untuk mendapatkan jawabannya dalam waktu yang lebih singkat).

Cara lain beberapa masalah telah diketahui batas bawah, adalah untuk membatasi model perhitungan.

Meskipun batas bawah semacam perbandingan tidak melebihi $\Omega (n\log n)$, Saya pikir ini layak untuk dibahas. Sortir perbandingan juga merupakan masalah yang memiliki batas bawah lebih besar daripada ukuran inputnya, tetapi batas bawahnya tidak melebihi$\Omega (n\log n)$, dan masuk . Namun, ketika saya sedang meneliti ini, saya menemukan pertanyaan ini pada mathoverflow: Kompleksitas waktu super-linier batas bawah untuk setiap masalah alami di NP . Contoh lebih lanjut tercantum dalam jawaban ada jauh di bawah$\Omega (n\log n)$. Saya pikir intinya adalah, jika Anda membatasi model perhitungan, Anda bisa mendapatkan batas yang lebih rendah untuk masalah yang tidak kita miliki. Dan jika Anda tidak membatasi model komputasi, sangat sulit untuk membuktikan batas bawah pada masalah.