Aplikasi topologi untuk ilmu komputer

Saya ingin menulis survei tentang aplikasi Topologi dalam Ilmu Komputer. Saya berencana untuk membahas sejarah ide-ide topologi dalam Ilmu Komputer dan juga menyoroti beberapa perkembangan saat ini. Akan sangat membantu jika ada yang bisa memberi masukan tentang pertanyaan di bawah ini.

1. Adakah tulisan atau catatan yang menggambarkan kronologi penggunaan topologi dalam Ilmu Komputer?

2. Apa aplikasi hasil terpenting dalam Topologi untuk Ilmu Komputer?

3. Apa bidang paling menarik dari pekerjaan saat ini yang menggunakan topologi untuk mendapatkan wawasan tentang komputasi?

Terima kasih!

Secara pribadi, saya pikir aplikasi topologi yang paling menarik adalah pekerjaan yang dilakukan oleh Herlihy dan Shavit. Mereka menggunakan topologi aljabar untuk mengkarakterisasi perhitungan terdistribusi asinkron dan memberikan bukti baru dari hasil penting yang diketahui dan merobohkan sejumlah masalah terbuka lama. Mereka memenangkan hadiah Godel 2004 untuk pekerjaan itu.

"Struktur Topologi Komputasi Asinkron" oleh Maurice Herlihy dan Nir Shavit, Jurnal ACM, Vol. 46 (1999), 858-923,

Topologi adalah disiplin yang matang dengan berbagai subbidang termasuk geometris, aljabar, metrik, point-set dan topologi pointless (mencela diri sendiri). Ilmu komputer juga cukup luas dan memiliki banyak sub-bidang matematika, jadi saya berharap banyak aplikasi ide-ide topologi di CS. Marshall Stone berkata "selalu melakukan topologi," dan para ilmuwan komputer dengan latar belakang yang diperlukan sering memilikinya. Cukup blah. Beberapa contoh.

Contoh-contoh ini bukan hanya masalah CS sulit diselesaikan oleh topologi. Kadang-kadang gagasan topologi ditransfer dengan sangat baik ke pengaturan CS atau memberikan dasar untuk sub area CS.

1. Teorema kekompakan dari logika proposisional adalah konsekuensi dari teorema Tychonoff. Kekompakan untuk logika urutan pertama biasanya terbukti berbeda. Kekompakan adalah alat penting dalam teori model klasik.

2. Teorema representasi batu untuk aljabar Boolean mengaitkan model logika proposisional, aljabar Boolean dan ruang topologi tertentu. Hasil dualitas tipe batu telah diturunkan untuk struktur yang digunakan dalam logika aljabar dan semantik bahasa pemrograman.

3. Nick Pippenger menerapkan teorema Stone ke aljabar Boolean untuk bahasa reguler dan menggunakan topologi untuk membuktikan beberapa fakta tentang bahasa biasa. Lihat komentar Jean-Eric Pin untuk pekerjaan terbaru tentang topologi dalam teori bahasa.

4. Dalam metode formal, ada gagasan tentang properti keselamatan dan kehidupan. Setiap properti linear-waktu dapat dinyatakan sebagai persimpangan dari properti safety dan liveness. Buktinya menggunakan topologi dasar.

5. Martín Escardó telah mengembangkan algoritma dan program tertulis untuk mencari set yang tidak terbatas. Saya percaya kekompakan adalah unsur utama dari pekerjaan itu.

6. Pekerjaan ahli topologi Polandia (seperti Kuratowski) memberi kami operator penutupan. Operator penutupan pada kisi adalah bagian penting dari teori interpretasi abstrak, yang mendasari analisis program statis.

7. Operator penutupan dan ide topologi lainnya adalah dasar dari morfologi matematika.

8. Gagasan operator interior juga dari sekolah Polandia adalah penting dalam aksiomatisasi logika modal.

9. Banyak ilmu komputer didasarkan pada struktur berbasis grafik. Beberapa aplikasi memerlukan gagasan yang lebih kaya tentang keterhubungan dan aliran daripada yang disediakan oleh grafik dan topologi adalah langkah selanjutnya. Ini adalah bacaan saya tentang automata dimensi tinggi van Glabbeek dalam teori konkurensi dan penerapan topologi geometris Eric Goubault pada semantik program bersamaan.

10. Mungkin aplikasi yang menerima paling banyak pers adalah aplikasi topologi (awalnya aljabar, meskipun lebih banyak presentasi kombinatorial juga ada) untuk mengkarakterisasi skenario toleransi kesalahan tertentu dalam komputasi terdistribusi. Selain Herlihy dan Shavit yang disebutkan di atas, Borowsky dan Gafni, dan Saks dan Zaharouglou juga memberikan bukti untuk terobosan pertama seperti itu. Kerangka kerja komputasi asinkron menghasilkan lebih banyak hasil tersebut.

11. Teorema poin tetap Brouwer telah memunculkan beberapa masalah yang kita pelajari. Baru-baru ini dalam studi teori permainan algoritmik, kelas kompleksitas PPAD dan kelas kompleksitas FixP masalah titik tetap.

12. Teorema Borsuk-Ulam memiliki beberapa aplikasi untuk membuat grafik dan embed metrik. Ini tercakup dalam buku Jiří Matoušek.

Ini adalah hasil yang sedikit dari apa yang ada di luar sana. Semoga berhasil!

$D\cong [D\to D]$$\lambda$-kalkulus. Semantik pada dasarnya didasarkan pada gagasan perkiraan, yang diberikan oleh pemesanan, dan solusi persamaan titik paling tidak tetap, dan solusi umumnya dijamin ada.

Berasal dari semantik denotasional adalah koneksi dengan interpretasi abstrak, dan analisis dan verifikasi program.

Penelitian saat ini termasuk menyediakan semantik denotasional untuk konkurensi dan bahasa kuantum.

Abramsky dan Jung memberikan survei bagus tentang ide-ide inti: Teori Domain .

Batas pada jumlah komponen yang terhubung, dan lebih umum nomor Betti, varietas semi-aljabar dan pengaturan hyperplane (dan pelengkapnya) telah digunakan untuk beberapa batas bawah pada perhitungan aljabar dan pohon keputusan. Untuk hanya beberapa referensi besar, lihat:

Michael Ben-Or, Batas bawah untuk pohon perhitungan aljabar, STOC 1983, hlm. 80-86.

Andrew Chi-Chih Yao, Kompleksitas pohon keputusan dan angka Betti, J. Comput. Sistem Sci. 55 (1997), no. 1, bagian 1, 36-43 (STOC 1994).

Anders Bjorner dan Laszlo Lovasz, pohon keputusan Linear, pengaturan ruang bagian dan fungsi Mobius, J. Amer. Matematika Soc. 7 (1994), no. 3, 677-706.

Dalam nada yang berbeda tetapi agak terkait, Smale menggunakan topologi dengan cara yang cukup menarik (khususnya, kohomologi kelompok kepang) untuk membatasi kompleksitas pencarian akar dalam model Blum-Shub-Smale:

Smale, S. Pada topologi algoritma, IJ Complexity, 3 (2): 81-89, 1987.

$2^{\omega}$

Ini terkait dengan jawaban dan teori domain Dave. Argumen dasar di sini adalah bahwa komputabilitas pada dasarnya didasarkan pada operasi lokal dan pengamatan terbatas . Anda dapat menganggap komputasi sebagai gagasan topologi yang disempurnakan. Contoh paling jelas adalah:

Semua fungsi yang dikomputasi (oracle Turing) bersifat kontinu. Di sisi lain, setiap fungsi kontinu adalah oracle Turing yang dapat dihitung dengan oracle yang cocok.

Anda dapat menemukan lebih banyak di buku Klaus Weihrauch "Analisis Komputasi". Anda mungkin juga ingin melihat buku bagus Steven Vickers yang disebut "Topologi via Logika".

Dua makalah lain yang mungkin relevan untuk survei Anda ...

M. Gehrke, S. Grigorieff, J.-E. Pin, Pendekatan topologi untuk pengakuan, ICALP 2010, Bagian II, Catatan Kuliah di Ilmu Komputer 6199, Springer Verlag, (2010), 151-162.

M. Gehrke, S. Grigorieff, J.-E. Pin, Dualitas, dan teori persamaan bahasa reguler, Penghargaan makalah terbaik ICALP 2008, Track B, ICALP 2008, Bagian II, Catatan Kuliah di Ilmu Komputer 5126, Springer Verlag, (2008), 246-257.

Jangan lupa dugaan Kneser dan bukti Kahn / Saks / Sturtevant untuk dugaan Aandera-Rosenberg-Karp.

Belum pernah disebutkan karya Robert Ghrist , sebelumnya di Illinois tetapi sekarang di U Penn, menerapkan topologi untuk hal-hal seperti jaringan sensor dan robot. Ini wawancara yang bagus .

Juga sangat terkait dengan pekerjaan Gunnar Carlsson dkk tentang penerapan topologi untuk analisis data .

Mungkin bukan STOC / FOCS TCS, tapi pasti ilmu komputer.

Teori untuk memahami konkurensi dan pemodelan perhitungan konkuren paling baik dipahami secara topologis. Terlepas dari karya terkenal oleh Herlihy dan Shavit pada struktur topologi komputabilitas async yang disebutkan dalam jawaban sebelumnya - Eric goubault telah melakukan pekerjaan pada pemodelan konkurensi dengan geometri dan pekerjaan Pratt pada aplikasi ruang Chu untuk konkurensi di grup Stanurrency Concurrency juga menarik Meskipun saya tidak terbiasa dengan pekerjaan mereka.

Semua pekerjaan dimulai oleh Kitaev pada pendekatan topologi ke komputer kuantum yang toleran terhadap kesalahan. Lihat kertas asli Kitaev atau, misalnya, catatan kuliah John Preskill .

Belum ada yang menyebutkan topologi aljabar langsung , yang sebenarnya dikembangkan untuk menyediakan kotak alat topologi aljabar yang cocok untuk studi konkurensi.

Ada juga beberapa pendekatan topologi dimensi rendah untuk topik dalam teori perhitungan, semuanya cukup baru:

• Berbagai pendekatan untuk penghitungan kuantum anyonic yang toleran terhadap kesalahan berdasarkan pada teori kepang. Lihat misalnya DI SINI dan DI SINI . Juga untuk jaringan perhitungan kuantum adiabatik DI SINI .
• Formalisme berbasis topologi diagram untuk kalkulus lambda (mis. DI SINI , halaman 46-48, dan DI SINI ) dan untuk kalkulus Milner pi ( DI SINI ).
• Menggunakan rangkaian kusut berwarna untuk memodelkan rekursi dan rantai Markov. Lihat misalnya DI SINI dan DI SINI . Bahkan terbukti (tidak dipublikasikan) bahwa setiap komputasi mesin Turing dan jaringan saraf orde pertama mana pun dapat dimodelkan dengan cara ini.
• Ada formalisme teoretis kategori yang lebih tinggi untuk perhitungan kuantum di mana diagram topologi mewakili perhitungan, dan diagram yang setara secara topologi mewakili prosedur yang berbeda dengan konten komputasi yang identik. Lihat DI SINI .

Beberapa aplikasi untuk metric embeddings.

Periksa buku ini oleh Matousek: http://kam.mff.cuni.cz/~matousek/akt.html

Lihat juga makalah ini:

• Bi-Lipschitz menanamkan ke dalam ruang Euclidean dimensi rendah, J. Matousek (1990) (Dia menggunakan teorema van Kampen untuk membuktikan batas bawah)
• Ketidakmungkinan untuk Metric Embeddings menjadi R ^ d, J. Matousek dan A. Sidiropoulos

Baca buku ini:

Lihat halaman web yang diarsipkan

Lihat buku ini, Kompleksitas Komputasi: Perspektif Kuantitatif, itu mempelajari ukuran beberapa kelas kompleksitas menggunakan alat topologi yang terbatas sumber daya.

$P$$NP$$P \ne NP$$NP-P$$NP$$NP-P$