Apakah benar-benar mungkin untuk membuktikan batas bawah?

Dengan adanya masalah komputasi, apakah tugas menemukan batas bawah untuk perhitungan seperti itu benar-benar mungkin? Saya kira itu bermuara pada bagaimana langkah komputasi tunggal didefinisikan dan model apa yang kita gunakan untuk bukti, tetapi mengingat itu, apakah kita benar-benar membuktikan batas bawah kemudian secara umum? Maksud saya adalah dapatkah kita membuktikan sesuatu seperti "masalah tidak dapat diselesaikan lebih cepat dari waktu " daripada "masalah dapat diselesaikan dalam waktu atau lebih cepat"?$X$$t(X)$$X$$t(X)$

Saya telah mencoba mencari informasi secara khusus tentang batas bawah dan bukti dari mereka, tetapi saya tidak dapat menemukan minat, rekomendasi mengenai buku / makalah / situs web tentang masalah ini?

Kami benar-benar dapat membuktikan hal-hal seperti itu.

Banyak masalah memiliki batas bawah yang sepele, seperti bahwa menemukan minimum satu set angka (yang tidak diurutkan / terstruktur dengan cara apa pun) membutuhkan setidaknya waktu. Buktinya sederhana: algoritma hipotetis yang berjalan dalam waktu tidak dapat memeriksa semua angka dalam input. Jadi jika kita menjalankan algoritma pada beberapa input, kita dapat mengamati bahwa itu tidak pernah memeriksa elemen input tertentu. Mengubah elemen itu ke minimum, kita bisa membuat algoritma gagal.Ω ( n ) o ( n $n$$\Omega(n)$$o(n)$

Batas bawah yang kurang sepele adalah batas bawah untuk menyortir dalam model berbasis perbandingan. Buktinya ada pada baris berikut: diberi input angka , adakemungkinan keluaran (input bisa berupa permutasi dari daftar yang disortir, sehingga output juga bisa berupa permutasi dari input). Jika kita terbatas hanya melakukan perbandingan, maka algoritma kami (rata-rata) perlu melakukan setidaknya perbandingan agar dapat memberikanoutput yang berbeda.$\Omega(n \log n)$$n$$n!$$\log_2(n!)=\Omega(n \log n)$$n!$

Batas bawah bahkan bisa lebih kuat. Ada beberapa masalah (terutama masalah ) yang memiliki batas bawah eksponensial. Masalah dalam kelas ini termasuk menghitung strategi optimal untuk permainan seperti catur (umum), catur dan go. Buktinya adalah melalui Teorema Time Hierarchy , yang menyatakan (tunduk pada beberapa batasan pada ):$EXPTIME$$f$

Diberikan fungsi , ada masalah komputasi yang dapat dipecahkan dalam waktu tetapi tidak dapat diselesaikan dalam waktu .$f$$O(f(n))$$o(\frac{f(n)}{\log n})$

Jadi pada dasarnya, jika Anda dapat memikirkan fungsi ada masalah yang membutuhkan banyak waktu untuk menyelesaikannya.$f$

Akhirnya, jalan lain untuk tidak membuktikan batas waktu yang lebih rendah tetapi sesuatu yang lebih kuat menunjukkan ketidakpastian masalah (misalnya berhenti, pasca korespondensi).

Iya itu mungkin. Contoh klasik adalah fakta bahwa setiap algoritma pengurutan berbasis perbandingan memerlukan perbandingan untuk mengurutkan daftar panjang .$\Omega(n\log n)$$n$

Namun, batas bawah tampaknya jauh lebih sulit untuk dibuktikan daripada batas atas. Untuk membuktikan bahwa ada algoritma penyortiran yang membutuhkan perbandingan , Anda hanya perlu menunjukkan algoritme seperti itu (merge sort - voila !). Tetapi untuk batas bawah, Anda harus menunjukkan bahwa tidak ada algoritma di kelas tertentu yang dapat menyelesaikan masalah Anda. Kesulitan melakukan itu diilustrasikan oleh fakta bahwa kita hanya tahu bahwa meskipun kita tahu bahwa setidaknya satu dari inklusi itu ketat ( oleh teorema hierarki ruang) dan kebanyakan orang berpikir mereka semua ketat.$O(n\log n)$

Di sisi lain, Ryan Williams memiliki makalah yang bagus (dan pembicaraan, yang saya dengar beberapa kali) yang disebut Algoritma untuk Sirkuit dan Sirkuit untuk Algoritma , di mana ia berpendapat bahwa menemukan batas bawah dan menemukan algoritma tidak secara mendasar semua berbeda. Sebagai contoh, ia mengutip bukti dari ketidakpastian masalah penghentian sebagai contoh dari algoritma (mesin Turing universal) yang digunakan tepat untuk membuktikan batas bawah (ketidakpastian).

Untuk mengambil contoh sepele, Anda tidak dapat menemukan angka terbesar dari sekumpulan angka tanpa memeriksa semuanya yang membutuhkan waktu linier. Tidak ada bukti besar. Tetapi ada algoritma yang tidak selalu mengharuskan membaca semua data. Contoh yang bagus adalah mencari semua kemunculan pola dalam sebuah string, yang mungkin tidak perlu membaca seluruh string (algoritma Boyer-Moore). Tetapi saya tidak boleh mengulangi apa yang sudah dijawab, mungkin lebih baik daripada saya.$n$

Namun, ada poin dalam pertanyaan yang menyerukan beberapa komentar lebih lanjut tentang batas bawah (atau batas kompleksitas pada umumnya).

Sebenarnya pilihan apa yang merupakan langkah komputasi tunggal tidak relevan, selama langkah-langkah komputasi dapat dianggap memiliki upperbound yang konstan (dan batas bawah). Hasil kerumitan akan sama karena didefinisikan hingga konstanta. Mengambil 3 perbandingan sebagai operasi unit, atau hanya satu, tidak ada bedanya.

Hal yang sama berlaku untuk ukuran data yang berfungsi sebagai referensi untuk mengevaluasi biaya perhitungan. Mengambil bilangan bulat tunggal, atau dua bilangan bulat sebagai satuan ukuran tidak ada bedanya.

Namun, kedua pilihan tersebut harus terkait.

Anda dapat mempertimbangkan bahwa angka adalah satu unit data jika Anda menganggap bahwa operasi pada bilangan bulat, seperti penambahan atau perbandingan, adalah operasi unit. Anda juga dapat mempertimbangkan bahwa itu adalah unit data karena dibutuhkan digit untuk mewakili angka. Kemudian, tentu saja, penambahan dan perbandingan bukan lagi unit operasi, dan biayanya tergantung pada nilai-nilai operan.$n$$\log n$$O(\log n)$

Apakah suatu operasi dapat dianggap memiliki biaya satuan terkait erat dengan data apa yang dapat dianggap memiliki ukuran satuan. Dan itu tergantung pada tingkat abstraksi yang Anda pilih untuk model perhitungan Anda.