Masalah yang terbukti membutuhkan waktu kuadratik

Saya mencari contoh masalah yang memiliki batas bawah ) untuk input . $\Omega(|x|^2$ $x$

Masalahnya perlu memiliki properti berikut:

$\Omega(n^2)$ bukti runtime untuk algoritma apa pun - prioritas pertama adalah memiliki sesederhana mungkin argumen batas bawah.
$O(n^2)$ Algoritma , jika memungkinkan, juga sederhana.
Ukuran keluaran (atau lebih kecil). Jelas setiap masalah yang membutuhkan output yang panjang diperlukan setidaknya waktu yang sama, tapi bukan itu yang saya cari. Perhatikan bahwa setiap masalah keputusan cocok di sini. $O(n)$ $\Omega(n^2)$
(jika mungkin) masalah "alami". Tanpa definisi formal, masalah yang akan diakui oleh lulusan CS lebih disukai.

Saya baru-baru ini ditanya tentang masalah seperti itu tetapi tidak dapat menemukan yang sederhana. Masalah pertama yang muncul di pikiran adalah , yang dikonstruksikan menjadi masalah runtime . Ini tidak cukup sederhana dan lebih jauh lagi, konstruksinya baru - baru ini terbukti salah : o. $3SUM$ $\Omega(n^2)$

Pergi ke masalah yang sangat tidak wajar, saya percaya bahwa masalah yang didapat sebagai input TM deterministik dan input , dan menampilkan posisi head tape setelah langkah-langkah saat dijalankan pada mungkin menjawab pertanyaan. $\langle M \rangle,x$ $(|M|+|x|)^2$ $x$

Jika Anda benar-benar perlu, mari kita sepakat bahwa kami menggunakan model TM single-tape, meskipun saya lebih suka masalah yang runtime independen pada model yang tepat (asalkan itu yang masuk akal).

Jadi, dapatkah kita menemukan masalah sederhana (untuk dibuktikan), alami (terkenal) yang runtime-nya ? $\Theta(n^2)$

complexity-theory turing-machines time-complexity lower-bounds BPR
sumber

Saya pikir "Mengingat bilangan asli , , hitung " memenuhi syarat. Perhatikan juga pertanyaan ini .

x

$x$

y

$y$

x + y

$x+y$

Raphael

Satu-satunya cara kita tahu bagaimana membuktikan batas bawah superlinear pada mesin Turing multitape adalah melalui diagonalisasi. Untuk mesin Turing single-tape, Anda bisa mendapatkan sedikit lebih baik menggunakan urutan persimpangan, tetapi tidak sejauh kecuali mungkin Anda membatasi ruang.

n^{2}

$n^2$

Yuval Filmus

Lihat di sini untuk pertanyaan terkait lainnya; masukan pembalikan tampaknya menjadi kandidat yang bagus.

Raphael

Saya tidak berpikir Anda bisa melakukannya dengan masalah keputusan, karena batas bawah NP terbaik yang ditemukan adalah O (n).

Albert Hendriks

Terima kasih atas komentar Anda @AlbertHendriks. Bisakah Anda berbagi referensi ke sumber / survei mengklaim bahwa yang paling dikenal lebih rendah menuju setiap masalah dalam NP adalah

Ω (n)

$\Omega(n)$

Jawaban:

Menemukan pemotongan kue iri bebas memerlukan query. Namun, ini tidak langsung menjawab pertanyaan Anda karena model komputasinya berbeda dari mesin Turing. $\Omega(n^2)$

Ngomong-ngomong, saat ini algoritma yang paling cepat diketahui untuk masalah ini membutuhkan query, jadi ada celah besar dari batas bawah - mungkin salah satu celah terbesar dalam ilmu komputer. $n^{n^{n^{n^{n^{n}}}}}$

Erel Segal-Halevi
sumber

Seperti pada tautan yang disediakan oleh Raphael, Peter menunjukkan bahwa Pembalikan Input membutuhkan $\Theta(n^2)$ waktu pada vanilla single-tape TMs. Untuk masalah keputusan, bahasa

L = {x 0^{| x |} x ∣ x \in {0, 1}^{*}}

$L = \{x0^{|x|}x \mid x \in \{0,1\}^\ast \}$ juga terbukti membutuhkan

Θ (n^{2})

$\Theta(n^2)$ waktu untuk menghitung. Untuk melihat ini, menggunakan argumen kompleksitas komunikasi Petrus, bersama dengan hasil klasik yang

E Q_{n}

$EQ_n$ kebutuhan

Θ (n)

$\Theta(n)$ bit komunikasi, untuk menunjukkan kuadrat batas bawah dari

L

$L$ . Pendekatan serupa bekerja untuk yang lebih alami

L = {x x ∣ x \in {0, 1}^{*}}

$L = \{xx \mid x \in \{0,1\}^\ast \}$ .

Ngomong-ngomong, perlu disebutkan bahwa "metode urutan persimpangan" yang disebutkan oleh Yuval adalah (setahu saya) secara matematis setara (atau, mungkin, inforior) dengan kompleksitas komunikasi satu.

$\mathsf{SAT}$ $O(n^{2 \cos(\pi/7)})$ $n^{o(1)}$ $2 \cos(\pi/7) \approx 1.8$

Lwin
sumber