Adakah algoritma yang terbukti ada meskipun kita tidak tahu apa itu?

21

Dalam matematika, ada banyak bukti keberadaan yang tidak konstruktif, jadi kita tahu bahwa ada objek tertentu meskipun kita tidak tahu bagaimana menemukannya.

Saya mencari hasil yang serupa dalam ilmu komputer. Secara khusus: apakah ada masalah yang dapat kita buktikan dapat diputuskan tanpa menunjukkan algoritme untuknya? Yaitu kita tahu bahwa itu dapat diselesaikan dengan suatu algoritma, tetapi kita tidak tahu seperti apa algoritma itu?

Erel Segal-Halevi
sumber
5
Ada jawaban yang sepele. Mengambil pertanyaan ya / tidak jawabannya dari yang unkown, seperti "adalah acak", maka pertanyaannya adalah decidable, hanya kita belum tahu yang mana dari dua algoritma yang mungkin adalah benar. π
Hendrik
6
pada dasarnya duplikat dari pertanyaan tcs.se apakah ada bukti keberadaan algoritma yang tidak konstruktif
vzn
1
@Babou Memang: pertanyaan dengan jawaban unik dapat dipilih. Di sini ketidaktahuan adalah intinya tampaknya, ini adalah kasus "tidak tahu" dari pertanyaan, meskipun hanya "tidak tahu sekarang ". Setelah kami mengetahui apakah itu acak atau tidak, kita perlu mencari contoh lain. Jawaban Anda di bawah ini tentu saja jauh lebih baik! Ini adalah bentuk "tidak tahu" yang secara inheren "tidak akan pernah tahu". π
Hendrik
1
@ HendrikJan: Dan prosedur itu adalah apa yang kita sebut algoritma dalam CS. Tetapi dengan mengambil masalah penghentian sebagai contoh, kita bahkan tidak dapat membuktikan bahwa suatu algoritma ada!
MSalters
1
Beberapa contoh yang lebih menarik dapat ditemukan di sini: cstheory.stackexchange.com/questions/4777/…
Erel Segal-Halevi

Jawaban:

14

Kasus paling sederhana yang saya tahu tentang suatu algoritma yang ada, meskipun tidak diketahui algoritma mana, menyangkut automata keadaan terbatas.

Hasil bagi dari bahasa L 1 oleh bahasa L 2 didefinisikan sebagai L 1 / L 2 = { x y L 2  sedemikian rupa sehingga  x y L 1 } .L.1/L.2L.1L.2L.1/L.2={xyL.2 seperti yang xyL.1}

Terbukti dengan mudah bahwa set reguler ditutup di bawah hasil bagi oleh set arbitrer. Dengan kata lain, jika adalah reguler dan L 2 adalah arbitrer (tidak harus reguler), maka L 1 / L 2 juga teratur.L.1L.2L.1/L.2

Buktinya cukup sederhana. Misalkan menjadi FSA yang menerima set reguler R , di mana Q dan F masing-masing adalah set negara dan set negara penerima, dan membiarkan L menjadi bahasa yang sewenang-wenang. Biarkan F = { q Q y LM.=(Q,Σ,δ,q0,F)RQFL. sebagai himpunan negara dari mana keadaan akhir dapat dicapai dengan menerima string dari L .F={qQyL.δ(q,y)F}L.

Otomat , yang berbeda dari M hanya di set F ' negara akhir mengakui tepatnya R / L . (Atau lihat Hopcroft-Ullman 1979, halaman 62 untuk bukti dari fakta ini.)M.=(Q,Σ,δ,q0,F)M.FR/L.

Namun, ketika himpunan tidak dapat ditentukan, mungkin tidak ada algoritma untuk memutuskan negara bagian mana yang memiliki properti yang mendefinisikan F . Jadi, sementara kita tahu bahwa himpunan F adalah subset dari Q , kita tidak memiliki algoritma untuk menentukan subset mana. Akibatnya, sementara kita tahu bahwa R diterima oleh salah satu dari 2 | Q | mungkin FSA, kita tidak tahu itu. Meskipun saya harus mengakui bahwa sebagian besar dari kita tahu seperti apa bentuknya.L.FFQR2|Q|

Ini adalah contoh dari apa yang kadang-kadang disebut bukti yang hampir konstruktif , yaitu bukti bahwa salah satu dari sejumlah jawaban yang terbatas adalah yang benar.

Saya kira perpanjangan dari itu bisa menjadi bukti bahwa salah satu dari sekian banyak jawaban adalah jawaban yang benar. Tapi saya tidak tahu. Saya juga tidak tahu bukti murni non-konstruktif bahwa beberapa masalah dapat diputuskan, misalnya hanya menggunakan kontradiksi.

babou
sumber
1
@DW saya bilang biasa, tapi L arbitrer . Itu tidak harus berulang secara berulang, atau teratur. Tidak ada properti L yang digunakan selain fakta bahwa ia adalah serangkaian string. Jika Anda tidak mempercayai saya, lihat Hopcroft-Ullman 1979, halaman 62.RLL
babou
Terima kasih. Ini adalah jawaban favorit saya karena bahasa yang dapat memutuskan tidak terbatas.
Erel Segal-Halevi
@ Babou, kesalahan saya, saya salah membaca apa yang Anda tulis. Kesalahan saya - maaf tentang itu. Saya telah mengedit posting Anda untuk membuat bagian yang saya salah pahami semoga lebih mudah.
DW
@DW Saya geli bahwa Anda punya masalah, tetapi itu terjadi pada saya juga. Tapi mungkin aku seharusnya lebih jelas. Ini tidak disengaja. Mengatakan itu karena beberapa matematikawan berpikir lebih elegan untuk menjadi samar. Terima kasih atas hasil editnya.
babou
12

Untuk memperluas komentar asli Hendrick, pertimbangkan masalah ini

Mengingat integer adalah ada lari dari n atau 7s lebih berturut-turut dalam ekspansi desimal π ?n0nπ

Masalah ini dapat diputuskan, karena salah satu dari dua kasus dapat memperoleh:

  1. Ada bilangan bulat yang ekspansi desimal π berisi deretan N berurutan 7, tetapi tidak lagi dijalankan.NπN
  2. Untuk setiap , perluasan π memiliki lari dari n 7s berturut-turut.nπn

Dalam kasus (1) algoritma keputusan untuk masalah adalah salah satunya

Jika jawab "tidak", jawab lain "ya".n>N

dan dalam kasus (2) algoritma akan menjadi

Jawab "ya".

Jelas masing-masing adalah algoritma keputusan; kami tidak tahu yang mana. Itu sudah cukup, meskipun, karena decidability hanya membutuhkan keberadaan dari sebuah algoritma, bukan spesifikasi yang algoritma untuk digunakan.

Rick Decker
sumber
+1 Ini adalah contoh langsung yang saya ingat profesor saya di Computability and Logic using. Sebagai contoh saya, karena tidak memerlukan banyak pengetahuan domain, jadi mudah untuk disampaikan.
Joshua Taylor
1
Untuk formulasi alternatif, lihat juga di sini .
Raphael
2

Ini bukan jawaban. Saya memposting karena saya percaya itu instruktif, karena saya awalnya mengklaim sebaliknya dan delapan orang cukup setuju untuk mengungguli sebelum @sdcwc menunjukkan kesalahan. Saya tidak ingin hanya mengedit jawaban pertama saya karena saya tidak yakin karena banyak orang akan membatalkannya jika mereka tahu itu salah.

Saya awalnya mengklaim bahwa itu sudah cukup untuk mengambil set  yang kita tahu terbatas tetapi yang kita tidak tahu anggota. Karena S  terbatas, ia bersifat rekursif, jadi ada algoritme tetapi saya menyatakan bahwa kami tidak tahu apa itu.SS

Namun, ini tidak benar. Sebagai contoh, oleh teorema Robertson-Seymour, kita tahu bahwa kelas grafik treewidth paling banyak 10 memiliki kumpulan anak-anak terlarang yang terbatas. Kami tidak tahu apa set ini jadi saya mengklaim kita tidak memiliki algoritma untuk memutuskan apakah grafik  adalah minor dilarang dari kelas grafik treewidth paling 10. Tapi poin @sdcwc bahwa ada adalah sebuah algoritma : cukup periksa bahwa H  memiliki treewidth lebih dari 10 dan semua anak di bawah umur yang tepat memiliki treewidth paling banyak 10.HH

David Richerby
sumber