Apakah ada masalah tanpa algoritma yang efisien, di mana teorema keberadaan telah membuktikan algoritma tersebut harus ada?

22

Apakah ada masalah dalam CS di mana tidak ada algoritma efisien yang diketahui, meskipun ada teorema yang membuktikan algoritma efisien seperti itu harus ada?

Apa sebutan masalah ini? Di mana saya bisa tahu lebih banyak?

ds.algorithms reference-request terminology z5h
sumber
4
Saya pikir ini relevan: en.wikipedia.org/wiki/Minor_(graph_theory)#Algorithms
Philip White
3
Apa pertanyaan Anda? Dalam judul mengatakan "solusi", tetapi dalam konten Anda menulis "algoritma".
Marcos Villagra
6
Saya pikir akan lebih baik jika Anda meminta masalah yang menarik / alami , jika tidak mudah untuk mendefinisikan masalah seperti itu: ambil pernyataan matematika yang tidak diketahui benar atau salah, buat masalah keluaran 1 (terlepas dari input) jika true dan 0 jika salah. Ada dua algoritma yang sangat sederhana yang salah satunya memecahkan masalah ini, tetapi memutuskan mana yang pada dasarnya membuktikan / menolak pernyataan matematika, jadi kita tidak tahu yang mana yang memecahkannya.
Kaveh

Jawaban:

9

Sebagai contoh, Shelby Kimmel menggunakan metode musuh dalam makalah ini untuk menunjukkan bahwa harus ada algoritma permintaan untuk masalah tertentu yang kita tidak tahu solusi kueri konstan. Dia melakukan ini dengan cara yang sangat apik dengan menemukan kompleksitas kueri dari masalah yang disusun dengan dirinya sendiri d kali dan kemudian menemukan kompleksitas kueri Q dari fungsi kompos, dan mencatat bahwa kompleksitas kueri dari fungsi asli adalah pesanan Q 1O(1)dQ .Q1d

Artem Kaznatcheev
sumber
12

Tentu, ada banyak contoh, setidaknya dalam semangat pertanyaan Anda.

Seringkali seseorang mendapatkan hasil seperti itu dari metode probabilistik . Sebagai contoh, satu kertas yang saya suka yang mengalami masalah adalah pada merekonstruksi grafik dalam model aditif . Di sini, penulis menunjukkan bahwa ada seperangkat kueri yang akan (secara optimal) mempelajari grafik target. Diberikan set ini, algoritma ini efisien. Namun, mereka menggunakan metode probabilistik untuk menunjukkan keberadaan set kecil ini (untuk setiap ukuran masalah) yang akan bekerja pada semua input, tetapi tidak secara eksplisit membangunnya. Jadi yang terbaik yang bisa mereka lakukan hanyalah pencarian dengan kekerasan melalui keluarga permintaan yang eksponensial karena mereka tidak memiliki konstruksi eksplisit.O(dn)

Lev Reyzin
sumber
2

Tidak, Anda selalu dapat menggunakan algoritma tercepat dan terpendek untuk semua masalah yang terdefinisi dengan baik . ;)

Marcus Ritt
sumber
Saya tidak benar-benar serius tetapi mengamati bahwa konstruksi Hutter sebenarnya membuktikan kebenaran algoritma. Menurut Anda mengapa itu tidak menjawab pertanyaan?
Marcus Ritt
4
@Ross Snider: tentu saja bahasa yang tidak dapat dipastikan lolos dari hasil Hutter: dia, bagaimanapun, memberikan algoritma! Namun, tidak seperti pencarian Levin, yang mengharuskan instance masalah memiliki sertifikat yang dapat diverifikasi (seperti masalah pencarian NP), pencarian Hutter tidak. Ini hanya mensyaratkan bahwa masalah dinyatakan dalam bahasa formal, yang dapat berfungsi sebagai dasar untuk mencari bukti [bahwa beberapa TM sebenarnya memecahkan masalah yang ditentukan]. Juga, Hutter / Levin tidak memberi kita bukti keberadaan algoritma yang efisien untuk suatu masalah kecuali kita sudah tahu bahwa masalahnya memiliki algoritma semacam itu.
Joshua Grochow
1
@ Joshua, saya menggunakan bahasa yang tidak dapat dipastikan sebagai contoh dari sesuatu yang tidak dapat diputuskan oleh pencarian Hutter / Levin (saya mencoba untuk memilih sesuatu yang jelas) tetapi yang tetap "didefinisikan dengan baik"; ini adalah argumen terhadap klaim yang diajukan dalam judul makalah ini. Tentu saja, saya berhati-hati untuk mengakui bahwa saya belum membaca isinya, yang harus saya lakukan sekarang.
Ross Snider
1
Apakah algoritma ini konten komputasi dari kesetaraan matematika konstruktif dan klasik pada pernyataan forall-exist?
Neel Krishnaswami
1
@Neel Kirshnaswami: Sulit dikatakan, karena saya tidak tahu ada persamaan seperti itu! Bisakah Anda memberikan pointer?
Joshua Grochow
1

Sunting: Jawaban di bawah ini adalah mengatur keberadaan solusi untuk masalah komputasi yang diberikan, bukan pada keberadaan algoritma. Awalnya, saya salah menafsirkan pertanyaan itu.

Menjawab

Ada kelas kompleksitas yang menangkap masalah komputasi semacam ini. Ini dikenal sebagai TFNP . Itu didefinisikan dalam makalah ini:

Nimrod Megiddo dan Christos Papadimitriou. Pada fungsi total, teorema keberadaan dan kompleksitas komputasi . Ilmu Komputer Teoritis 81 (2): 317-324.

Di sini Anda akan menemukan masalah seperti Trichromatic Triangle, yang keberadaan solusinya dijamin oleh Sperner's Lemma (lihat makalah untuk definisi masalah ini).

Anda juga memiliki kertas berikut:

Christos Papadimitriou. Tentang Kompleksitas Argumen Paritas dan Bukti Keberadaan Lainnya yang Tidak Efisien . Jurnal Ilmu Komputer dan Sistem 48 (3), 1990.

Dalam tulisan ini Anda akan menemukan:

  • n lemma berdimensi Sperner, yang merupakan generalisasi dari trikromatik Segitiga.
  • Keseimbangan game 2-pemain.
  • Temukan jalur hamiltonian kedua pada grafik.

Makalah ini memiliki banyak contoh masalah jenis ini. Jadi saya sarankan untuk melihatnya.

Marcos Villagra
sumber
2
Pertanyaannya bukan tentang masalah dengan solusi yang sudah terbukti untuk versi keputusan mereka tetapi tentang masalah dengan keberadaan algoritma yang terbukti efisien. Ini adalah hal yang berbeda. Saya setuju bahwa pada pandangan pertama judul itu bisa menyesatkan. Namun, hanya pada pandangan pertama.
Oleksandr Bondarenko
ya saya juga setuju. Tetapi saya benar-benar disesatkan oleh pertanyaan itu. Sekarang dalam kasus ini, jawabannya menyesatkan. Apa yang saya lakukan? Apakah saya menghapus pertanyaan? Atau edit dan beri peringatan tentang apa yang sebenarnya menjawab?
Marcos Villagra
Tidak ada kebijakan untuk menghapus jawaban, Anda selalu dapat melakukan apa yang Anda anggap tepat. Secara pribadi saya pikir tidak apa-apa meninggalkan jawaban Anda di sini. Anda dapat memberikan pernyataan tentang pertanyaan mana yang Anda jawab dengan tepat.
Hsien-Chih Chang 張顯 之