Masalah perhitungan yang sangat besar tapi terbatas secara lokal

14

Pertanyaan ini terinspirasi oleh komentar Jukka Suomela yang dibuat pada pertanyaan lain .

Apa saja contoh dari masalah perhitungan yang sangat besar tapi terbatas secara lokal (dan algoritma)?

Dengan kata lain, apa saja contoh perhitungan yang berhenti dalam waktu yang terbatas, di mana setiap Mesin Turing membaca dan memproses hanya data yang terbatas, tetapi secara keseluruhan perhitungan memecahkan masalah ukuran tak terbatas jika ada banyak mesin Turing yang terhubung dalam jaringan yang tak terbatas?

Aaron Sterling
sumber
Saya akan berkomentar bahwa ide ini tampaknya sama dengan TM tunggal dengan banyak kaset, yang saya pikir pernah saya lihat sebelumnya, tetapi sekarang saya tidak dapat menemukan referensi. Apakah saya bermimpi atau ini ide yang dieksplorasi? Tentu saja ekstensi penghitungan hiper-lain seperti TM waktu tak terbatas telah dipelajari. Apakah gagasan "jaringan" TM menambahkan sesuatu ke model ini?
Huck Bennett
@HuckBennett: Saya tidak tahu; mungkin sama. Saya mendapat pengertian dari komentar asli Jukka bahwa ia sedang memikirkan masalah seperti Grafik Pewarnaan pada grafik tak terbatas dengan derajat terikat (meskipun saya tidak tahu apakah masalah khusus itu akan menjadi jawaban untuk pertanyaan ini). Setiap TM akan menjalankan algoritma yang sama, dan berbicara dengan tetangga yang terbatas. Tampaknya TM dengan kaset yang tak terhingga banyaknya mungkin dapat mensimulasikan grafik dengan tepi yang sangat banyak di antara dua node, yang pada prinsipnya berbeda dengan apa yang ada dalam pikiran saya. Saya tahu sedikit tentang model seperti itu.
Aaron Sterling

Jawaban:

13

Hanya untuk memberikan beberapa ide tentang apa yang mungkin (tapi agak non-sepele), berikut adalah salah satu contohnya: algoritma terdistribusi yang menemukan pengemasan tepi maksimal pada grafik derajat terbatas.

Definisi masalah

Diberikan grafik sederhana tidak terarah , pengepakan tepi (atau pencocokan fraksional) mengaitkan bobot w ( e ) dengan masing-masing tepi e E sedemikian rupa sehingga untuk setiap simpul v V , total berat tepi yang terjadi pada v paling banyak 1 . Sebuah simpul jenuh jika bobot total tepi insiden sama dengan 1 . Pengepakan tepi maksimal jika semua tepi memiliki setidaknya satu titik akhir jenuh (yaitu, tidak ada beban yang dapat diperpanjang dengan rakus).G=(V,E)w(e)eEvVv11

Perhatikan bahwa pencocokan maksimal mendefinisikan pengemasan tepi maksimal (set w ( e ) = 1 iff e M ); karenanya mudah untuk diselesaikan dalam pengaturan terpusat klasik (dengan asumsi G adalah terbatas).MEw(e)=1eMG

Pengepakan tepi sebenarnya memiliki beberapa aplikasi, setidaknya jika seseorang mendefinisikan aplikasi dalam pengertian TCS yang biasa: himpunan node jenuh membentuk perkiraan dari penutup vertex minimum (tentu saja ini hanya masuk akal dalam kasus G terbatas ) .2G

Model perhitungan

Kami akan menganggap bahwa ada konstanta global sedemikian rupa sehingga derajat v V paling banyak adalah Δ .ΔvVΔ

Untuk menjaga agar ini sedekat mungkin dengan semangat pertanyaan awal, mari kita mendefinisikan model perhitungan sebagai berikut. Kami berasumsi bahwa setiap node adalah mesin Turing, dan edge { u , v } E adalah saluran komunikasi antara u dan v . Pita input v mengkodekan derajat deg ( v ) dari v . Untuk setiap v V , insiden tepi ke v diberi label (dalam urutan acak) dengan bilangan bulat 1 , 2 , vV{u,v}Euvvdeg(v)vvVv ; ini disebutlabel tepi lokal(label { u , v } E dapat berbeda untuk u dan v ). Mesin memiliki instruksi untuk dapat mengirim dan menerima pesan melalui masing-masing tepi ini; mesin dapat mengatasi tetangganya dengan menggunakan label tepi lokal.1,2,,deg(v){u,v}Euv

Kami mengharuskan mesin menghitung tepi valid kemasan untuk G . Lebih tepatnya, setiap v V harus mencetak pada pita keluarannya suatu pengkodean w ( e ) untuk setiap tepi dan insiden ke v , dipesan oleh label tepi lokal, dan kemudian berhenti.wGvVw(e)ev

Kami mengatakan bahwa algoritma terdistribusi menemukan pengemasan tepi maksimal dalam waktu T , jika berikut ini berlaku untuk setiap grafik G dengan derajat maksimum Δ , dan untuk setiap pelabelan tepi lokal G : jika kami mengganti setiap simpul G dengan salinan identik mesin Turing A dan nyalakan mesin, lalu setelah langkah T semua mesin telah mencetak solusi yang valid (konsisten secara global) dan berhenti.ATGΔGGAT

Infinities

Sekarang semua hal di atas masuk akal bahkan jika himpunan node tak terhitung jumlahnya.V

Perumusan masalah dan model perhitungan tidak memiliki referensi ke , langsung atau tidak langsung. Panjang input untuk setiap mesin Turing dibatasi oleh konstanta.|V|

Apa yang diketahui?

Masalahnya dapat diselesaikan dalam waktu yang terbatas bahkan jika tidak terbatas.G

Masalahnya adalah non-sepele dalam arti bahwa beberapa komunikasi diperlukan. Selain itu, waktu berjalan tergantung pada . Namun, untuk setiap tetap Δ , masalah dapat diselesaikan dalam waktu yang konstan terlepas dari ukuran G ; khususnya, masalahnya dapat dipecahkan pada grafik yang sangat besar.ΔΔG

Saya belum memeriksa apa waktu berjalan paling dikenal dalam model yang didefinisikan di atas (yang bukan model yang biasa digunakan di lapangan). Namun demikian, waktu berjalan yang polinomial dalam harus cukup mudah untuk dicapai, dan saya pikir waktu berjalan yang sublinear dalam Δ tidak mungkin.ΔΔ

Jukka Suomela
sumber
3

Menemukan generasi berikutnya dari Cellular Automaton .

Ini dapat diselesaikan seperti yang Anda gambarkan dalam waktu yang konstan. (Yaitu, independen dari input)


sumber
Saya pikir diperlukan lebih banyak perhatian untuk benar-benar merumuskan masalah komputasi (non-sepele, menarik) yang dapat diselesaikan dalam waktu terbatas menggunakan automata seluler?
Jukka Suomela
1
Saya setuju dengan @Jukka. Saya menganggap versi saat ini dari jawaban ini berada pada tingkat komentar, dan bukan yang informatif. Itu tidak menggambarkan masalah komputasi atau algoritma. Diturunkan.
Aaron Sterling
2

Pada dasarnya, setiap masalah yang setidaknya sama sulitnya dengan pewarnaan membutuhkan algoritma dengan waktu berjalan tergantung pada jumlah node dalam jaringan dan dengan demikian tidak dapat bekerja dalam grafik tak terbatas tetapi terbatas secara lokal. Ini mengikuti dari log mani Linial * n batas bawah.

Peter
sumber
2
Tapi apa sebenarnya model perhitungan Anda di sini? Linial mengasumsikan bahwa semua node memiliki pengidentifikasi numerik yang unik; jika kita mencoba memetakannya ke pengaturan yang disarankan dalam pertanyaan asli, kita akan memiliki mesin Turing yang diberi pengidentifikasi numerik mereka pada kaset input mereka. Tapi sekarang ukuran pengidentifikasi tidak terikat; hanya menunggu sampai semua mesin membaca pengenal mereka sendiri membutuhkan waktu yang sangat lama. Saya berpendapat bahwa hambatannya sebenarnya bukan batas bawah Linial, tetapi itu adalah model perhitungan: pengidentifikasi unik adalah model yang salah ketika kita berurusan dengan ketidakterbatasan.
Jukka Suomela
1
@ Jukka: Saya membayangkan sebuah sistem di mana semua prosesor anonim ketika saya menulis pertanyaan, tepatnya untuk menghindari ID yang tumbuh tanpa batas. Tetapi sekarang bagi saya mungkin ada masalah nontrivial di sini. Jika Anda memilih ukuran program dan beberapa fungsi yang dapat dihitung yang membatasi ukuran lingkungan prosesor mana pun, maka mungkin musuh yang sangat kuat dapat memilih serangkaian ID yang besar tetapi terbatas sehingga batas Linial masih menjadi faktor entah bagaimana. Musuh mungkin perlu untuk dapat menghitung fungsi yang tumbuh lebih cepat dari fungsi yang dapat dihitung untuk melakukan hal ini.
Aaron Sterling
0

AC0AC0

Joshua Grochow
sumber