Fisika menghasilkan TCS?

Tampak jelas bahwa sejumlah subbidang ilmu komputer teoretis telah secara signifikan dipengaruhi oleh hasil-hasil dari teori fisika. Dua contohnya adalah

1. Perhitungan kuantum
2. Hasil mekanika statistik digunakan dalam analisis kompleksitas / algoritma heuristik.

Jadi pertanyaan saya, adakah bidang utama yang saya lewatkan?

Motivasi saya sangat sederhana: Saya seorang fisikawan teoretis yang datang ke TCS melalui informasi kuantum dan saya ingin tahu tentang bidang-bidang lain di mana kedua bidang tersebut tumpang tindih.

Ini adalah pertanyaan yang relatif lunak, tetapi saya tidak bermaksud ini menjadi pertanyaan jenis daftar besar. Saya mencari daerah di mana tumpang tindihnya signifikan.

Teknik pencarian anil yang disimulasikan terinspirasi oleh proses fisik anil dalam metalurgi.

Annealing adalah perawatan panas di mana kekuatan dan kekerasan zat yang sedang dirawat dapat berubah secara dramatis. Seringkali ini melibatkan memanaskan bahan ke suhu ekstrem dan kemudian membiarkannya dingin perlahan.

Annealing simulasi menghindari minima / maxima lokal di ruang pencarian dengan memasukkan tingkat keacakan (suhu) dalam proses pencarian. Saat proses pencarian berlangsung, suhu secara bertahap mendingin, yang berarti bahwa jumlah keacakan dalam pencarian berkurang. Ternyata itu adalah teknik pencarian yang cukup efektif.

Bertolak belakang (dari TCS ke fisika), status produk matriks, PEPS (proyeksi status pasangan terjerat), MERA (ansatz renumerisasi keterjeratan multiskala) telah banyak diinformasikan oleh gagasan TCS yang diadaptasi dalam teori informasi kuantum. Akronim ini adalah semua teknik untuk mendekati keadaan sistem spin kuantum yang digunakan oleh ahli teori materi terkondensasi, dan dalam banyak kasus teknik ini tampaknya bekerja lebih baik daripada alat apa pun yang dikenal sebelumnya.

Sistem kompleks adalah bidang yang banyak berkaitan dengan analisis jaringan sosial, dan jaringan pada umumnya, dan telah diserbu oleh fisikawan dalam jumlah besar, menggunakan senjata dari statistik dan termodinamika. Apakah itu diserang oleh fisika adalah cerita yang berbeda.

Hasil dari Pour-El dan Richards Adv. Matematika 39 215 (1981) memberikan adanya solusi nonkomputasi pada persamaan gelombang 3D untuk kondisi awal yang dapat dihitung dengan menggunakan gelombang untuk mensimulasikan mesin Turing universal.

Koneksi juga sebaliknya. Beberapa waktu yang lalu, para ilmuwan komputer teoretis yang bekerja dalam teori domain mulai tertarik pada relativitas. Mereka membuktikan hasil tentang bagaimana merekonstruksi struktur ruangwaktu dari struktur kausalitas. Ini adalah sesuatu yang cukup akrab bagi para ahli teori domain, di mana objek-objek beasic yang menarik adalah perintah parsial yang topologinya ditentukan oleh urutan tersebut. Anda mungkin melihat http://www.cs.mcgill.ca/~prakash/Pubs/dom_gr_review.pdf

Contoh yang sangat lama (yang dapat digolongkan oleh jawaban Suresh, bagaimanapun, ini adalah cara yang berbeda) adalah pengaruh teori jaringan listrik, misalnya hukum sirkuit Kirchhoff, pada kombinatorik, teori grafik, dan probabilitas.

Satu area yang telah melihat beberapa aplikasi, tetapi tidak cukup IMO adalah mendekati struktur atau proses diskrit dengan perkiraan analitik. Ini adalah bisnis besar dalam matematika (misalnya, teori bilangan analitik) dan fisika (semua mekanika statistik), tetapi belum terbukti populer di CS karena beberapa alasan.

Aplikasi terkenal ini adalah dalam desain Mesin Koneksi. Ini adalah mesin paralel besar-besaran, dan sebagai bagian dari desainnya mereka perlu mencari tahu seberapa besar untuk membuat buffer di router. Feynman memodelkan router dengan PDE, dan menunjukkan buffer bisa lebih kecil daripada argumen induktif tradisional. Danny Hillis menceritakan kisah dalam esai ini .

Teori Gauge untuk pendekatan heuristik untuk pemrograman integer (beberapa makalah Misha Chertkov ). Metode kelompok renormalisasi untuk penghitungan kombinatorik, Ch.10-12 dari "Elements of the Random Walk" karya Rudnick / Gaspari. Menerapkan dekomposisi integral jalur Feymann (yaitu, Bagian 9.5.1) untuk menghitung jalan yang menghindari diri sendiri. Untuk koneksi ke TCS, perhatikan bahwa rezim traktabilitas untuk perkiraan penghitungan pada grafik tergantung pada tingkat pertumbuhan jalan kaki yang menghindari diri sendiri.

Fisika statistik telah memberikan para ilmuwan komputer cara baru dalam memandang SAT, seperti yang diulas di sini . Idenya adalah bahwa ketika rasio klausa terhadap variabel yang terlibat dalam rumus 3-SAT meningkat dari sekitar 4 menjadi sekitar 5 kita beralih dari mampu menyelesaikan sebagian besar contoh 3-SAT menjadi mampu menyelesaikan sangat sedikit. Transisi ini dianggap sebagai "perubahan fase" dalam SAT.

Gagasan ini mendapat ketenaran khusus selama musim panas ini dari dugaan makalah P vs NP Deolalikar.

Teori sistem terdistribusi awal, terutama makalah oleh Leslie Lamport et al., Telah memiliki beberapa dampak dari Relativitas Khusus untuk mendapatkan gambaran gambar yang benar untuk perjanjian (toleran-kesalahan) pada keadaan sistem global. Lihat entri 27. ( Waktu, Jam, dan Pengaturan Acara dalam Sistem Terdistribusi , Komunikasi ACM 21, 7 (Juli 1978), 558-565) dalam Tulisan Leslie Lamport , di mana Lamport memberikan informasi latar belakang berikut tentang bukunya. kertas:

Asal makalah ini adalah catatan berjudul The Maintenance of Duplicate Databases oleh Paul Johnson dan Bob Thomas. Saya percaya catatan mereka memperkenalkan ide menggunakan cap waktu pesan dalam algoritma terdistribusi. Kebetulan saya memiliki pemahaman yang mendalam dan mendalam tentang relativitas khusus (lihat [5]). Ini memungkinkan saya untuk segera memahami esensi dari apa yang mereka coba lakukan. Relativitas khusus mengajarkan kepada kita bahwa tidak ada urutan total kejadian yang tidak berubah dalam ruang-waktu; pengamat yang berbeda dapat tidak setuju tentang mana dari dua peristiwa yang terjadi terlebih dahulu. Hanya ada urutan parsial di mana peristiwa e1 mendahului peristiwa e2 jika if e1 dapat mempengaruhi e2. Saya menyadari bahwa esensi dari Johnson dan Thomas Algoritma s adalah penggunaan cap waktu untuk menyediakan urutan total peristiwa yang konsisten dengan urutan kausal. Realisasi ini mungkin brilian. Setelah menyadarinya, yang lainnya sepele. Karena Thomas dan Johnson tidak mengerti persis apa yang mereka lakukan, mereka tidak mendapatkan algoritma yang tepat; algoritma mereka memungkinkan perilaku aneh yang pada dasarnya melanggar kausalitas. Saya dengan cepat menulis catatan singkat yang menunjukkan hal ini dan memperbaiki algoritme.

Saya telah menyempurnakan jawaban ini dengan jawaban yang diperluas pada MathOverflow ke pertanyaan wiki komunitas Gil Kalai "[Apa itu] Buku yang Ingin Anda Tulis ."

Jawaban yang diperluas berusaha untuk menghubungkan masalah mendasar dalam TCS dan QIT dengan masalah praktis dalam penyembuhan dan pengobatan regeneratif.

• Joseph M. Landsberg's Geometry dan kompleksitas multiplikasi matriks (2008)

• Teori Symplectic Alvaro Pelayo dan San Vu Ngoc tentang sistem Hamilton yang sepenuhnya terintegrasi

Arena matematika untuk survei Landsberg adalah varietas yang terpisah dari varietas Segre , sementara arena untuk survei Pelayo dan Ngoc adalah manifold symplectic empat-dimensi… diperlukan beberapa saat untuk menghargai bahwa kedua arena ini keduanya merupakan keadaan produk matriks, sebagaimana masing-masing dilihat dari perspektif komputasi (Landsburg) dan perspektif geometris (Palayo dan Ngoc). Selain itu, Palayo dan Ngoc memasukkan dalam survei mereka sebuah diskusi tentang studi semi-klasik Babelon, Cantini, dan Douçot tentang model Jaynes-Cummings (mencatat bahwa model Jaynes-Cummings sering dijumpai dalam literatur fisika benda terkondensasi dan komputasi kuantum ).

Masing-masing referensi ini jauh untuk menerangi yang lain. Secara khusus, telah membantu dalam perhitungan dinamik spin kita sendiri (sangat praktis) untuk menghargai bahwa ruang-ruang kuantum yang dijelaskan secara berbeda dalam literatur sebagai status jaringan tensor, status produk matriks, dan varietas jarak varietas Segre kaya dianugerahi dengan singularitas yang struktur aljabar, symplectic, dan Riemannian saat ini dipahami dengan sangat tidak lengkap (seperti ulasan Pelayo dan Ngoc).

Untuk tujuan rekayasa kami, pendekatan geometri Landsburg / aljabar , di mana ruang-ruang dinamika kuantum dipandang sebagai variasi aljabar dan bukan ruang vektor, muncul sebagai yang paling alami secara matematis. Ini mengejutkan bagi kami, tetapi secara umum dengan banyak peneliti, kami menemukan bahwa toolset aljabar geometrik secara efektif memuaskan dalam memvalidasi dan mempercepat simulasi kuantum praktis.

Simulasiis kuantum saat ini menikmati keadaan yang membingungkan bahwa simulasi kuantum numerik besar seringkali berkinerja jauh lebih baik daripada yang kita ketahui alasan yang diharapkan. Ketika ahli matematika dan fisikawan mencapai pemahaman bersama, kebingungan ini pasti akan berkurang dan kenikmatan pasti akan tetap ada. Baik! :)

Algoritma menggambar grafik berbasis kekuatan adalah contoh lain. Idenya adalah untuk mempertimbangkan setiap tepi menjadi pegas dan tata letak node grafik sesuai dengan menemukan keseimbangan dalam koleksi pegas.

Banyak matematika yang kami gunakan awalnya diciptakan untuk memecahkan masalah fisika. Contohnya termasuk kalkulus (gravitasi Newton) dan deret Fourier (persamaan panas).

Ada makalah baru-baru ini yang menetapkan koneksi antara Keamanan Komputer dan prinsip ke-2 termodinamika.
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6266166

Konsep potensial terkait dengan berbagai bidang fisika. Dalam cs, potensi digunakan dalam analisis struktur data yang diamortisasi. Kita dapat melihat bagaimana setiap langkah mempengaruhi entropi sistem dan karenanya mendapatkan biaya operasi rata-rata (diamortisasi) dengan struktur data yang diberikan. Ini telah memunculkan banyak struktur data yang secara teoritis lebih baik seperti tumpukan fibonacci.

untuk menambah / mengisi beberapa celah dalam jawaban / cakupan luar biasa saat ini — tampaknya ada hubungan kuat antara TCS dan termodinamika dalam berbagai cara yang belum sepenuhnya dieksplorasi tetapi merupakan batas-batas penelitian aktif. ada titik transisi yang terkait dengan SAT tetapi tampaknya mungkin ada titik transisi yang terkait dengan kelas kompleksitas lainnya (atau bahkan semua) juga. titik transisi SAT dikaitkan dengan perbedaan antara instance "mudah" (P) dan "keras" (NP), tetapi bisa dibilang semua batas kelas kompleksitas harus mengarah ke properti seperti titik transisi yang sama.

pertimbangkan Mesin Turing. sudah mengukur operasinya dalam dimensi fisik biasanya "waktu" dan "ruang". tetapi perhatikan bahwa itu tampaknya juga melakukan satu unit "kerja" dalam bergerak dari kotak ke kotak dan membuat transisi. dalam fisika satuan kerja adalah Joule, yang juga merupakan ukuran energi. sehingga tampak bahwa kelas kompleksitas memiliki hubungan dengan tingkat energi, batas, atau rezim.

Teori mekanika kuantum semakin melihat ruang dan waktu itu sendiri, alam semesta, sebagai semacam sistem komputasi. tampaknya ia memiliki beberapa "unit komputasi minimal" yang sifatnya intrinsik, mungkin terkait dengan panjang Plank. jadi pemeriksaan mesin Turing minimal untuk masalah juga menyiratkan dan berhubungan dengan sistem fisik / energi minimal atau bahkan volume ruang yang diperlukan. [3]

juga, konsep kunci entropi muncul berulang kali dalam TCS dan fisika / termodinamika dan mungkin merupakan prinsip pemersatu dengan penelitian yang lebih aktif yang mengungkapkan sifat dasarnya. [1,2]

[1] entropi dalam teori informasi , wikipedia

[2] apa definisi CS dari entropi , stackoverflow

[3] Apa itu Volume Informasi? tcs.se