🙆🏻 🤠 🌙 Bukti signifikan dari teorema pada ilmu komputer menangkap fisika dengan matematika 🕊️ 🤽🏽 🏳️

Spesialis dalam ilmu komputer telah mengidentifikasi batas-batas baru dalam pengetahuan yang diverifikasi melalui perhitungan. Dan pada saat yang sama mereka memecahkan masalah signifikan dari mekanika kuantum dan matematika murni.

Pada tahun 1935, Albert Einstein, bersama dengan Boris Podolsky dan Nathan Rosen, mencoba untuk mengatasi peluang yang membuka dengan hukum fisika kuantum baru: "keterjeratan" dua partikel, yang dalam hal ini dapat dipisahkan oleh jarak yang sangat jauh.

Tahun berikutnya, Alan Turing merumuskan teori perhitungan umum pertama dan membuktikan adanya masalah, pada prinsipnya tidak tunduk pada komputer.

Kedua ide ini telah merevolusi bidangnya masing-masing. Selain itu, sepertinya mereka tidak ada hubungannya satu sama lain. Namun, sekarang bukti signifikan menyatukan mereka, secara bersamaan menyelesaikan banyak masalah dari ilmu komputer, fisika dan matematika.

Bukti baru menunjukkan bahwa komputer kuantum yang melakukan perhitungan menggunakan bit kuantum, atau "qubit," bukan nol dan klasik, secara teoritis dapat digunakan untuk mengkonfirmasi solusi untuk sejumlah besar masalah. Koneksi antara keterikatan kuantum dan teknologi komputer mengejutkan bagi banyak peneliti.

“Benar-benar tidak terduga,” kata Miguel Navazquezmempelajari fisika kuantum di Institut Optik Quantum dan Informasi Quantum di Wina.

Co-penulis bukti memutuskan untuk menentukan batas-batas kemungkinan mengkonfirmasi solusi untuk masalah komputasi. Pendekatan mereka menggunakan kebingungan. Setelah menemukan batas-batas ini, para peneliti pada saat yang sama, sebagai efek samping, menjawab dua pertanyaan lain: masalah Zirelson dalam fisika mengenai pemodelan keterjeratan matematis, dan masalah terkait matematika murni, hipotesis Conn tentang bersarang.

Hasilnya akhirnya jatuh seperti kartu domino.

“Semua ide orisinal lahir pada waktu yang hampir bersamaan. Sangat nyaman bahwa mereka semua berkumpul bersama dengan cara yang menakjubkan, "kata Henry Ewandari University of Toronto, salah satu penulis bukti. Penulis lain: Zhengfeng Ji dari University of Technology Sydney, Anand Natarajan dan Thomas Widick dari California Institute of Technology, dan John Wright dari University of Texas di Austin. Kelima adalah ilmuwan komputer.

Tugas tidak larut

Turing mengidentifikasi platform utama untuk studi komputasi bahkan sebelum munculnya komputer itu sendiri. Dan secara langsung dia menunjukkan bahwa komputer, pada prinsipnya, tidak dapat memecahkan masalah tertentu - dan ini dapat dibuktikan. Masalahnya adalah apakah program yang memecahkan masalah tertentu akan berhenti bekerja.

Biasanya, program komputer menerima data input dan setelah beberapa waktu menghasilkan data output. Tetapi kadang-kadang mereka terjebak dalam siklus tanpa akhir, yang membuat roda gigi mereka berputar selamanya. Ketika ini terjadi pada Anda, Anda hanya memiliki satu opsi tersisa.

“Saya harus memakukan program secara manual. Hentikan dia, ”kata Ewan.

Turing membuktikan bahwa tidak ada algoritma umum yang dapat menentukan apakah suatu program akan menyelesaikan eksekusi atau bekerja selamanya. Untuk mengetahuinya, Anda harus menjalankan program itu sendiri.

Ewan, Vidik, Ji, Natarajan dan Wright

“Anda menunggu satu juta tahun, dan program tidak selesai bekerja. Apakah Anda perlu menunggu jutaan tahun lagi? Tidak ada jawaban untuk pertanyaan ini, ”kata William Slofstra , ahli matematika di Universitas Waterloo.

Secara teknis, tugas menghentikan sebuah program tidak dapat dipecahkan - bahkan komputer paling kuat yang dapat Anda bayangkan tidak dapat menyelesaikannya.

Setelah Turing, para ilmuwan komputer mulai mengklasifikasikan tugas-tugas lain sesuai dengan kompleksitasnya. Tugas yang lebih kompleks membutuhkan lebih banyak sumber daya komputasi untuk dipecahkan - lebih banyak waktu untuk bekerja, lebih banyak memori. Jadi mempelajari kompleksitas tugas komputasi.

Sebagai hasilnya, Anda dapat mengajukan dua pertanyaan tentang setiap tugas: "Seberapa sulit untuk menyelesaikannya?" dan "Seberapa sulitkah untuk memverifikasi jawaban yang benar?"

Interogasi untuk konfirmasi

Dalam hal tugas-tugas sederhana, jawabannya dapat diperiksa secara independen. Tetapi karena mereka menjadi lebih rumit, bahkan memeriksa jawabannya dapat menjadi tugas yang mustahil. Namun, pada tahun 1985, para ilmuwan komputer menyadari bahwa itu mungkin untuk memverifikasi kebenaran jawabannya, bahkan jika itu mustahil untuk mengkonfirmasi sendiri.

Metode ini mengikuti logika penyelidikan polisi. Jika tersangka menceritakan kisah yang membingungkan, Anda mungkin tidak dapat pergi dan memeriksa setiap detailnya. Tetapi dengan mengajukan pertanyaan yang tepat, Anda dapat menangkap tersangka dalam kebohongan, atau Anda dapat diyakinkan akan kebenaran cerita.

Dalam hal informatika, interogasi berisi komputer yang kuat yang menawarkan solusi untuk masalah - yang dikenal sebagai "prover" - dan komputer yang kurang kuat yang menanyakan prover pertanyaan untuk menentukan kebenaran jawaban, yang dikenal sebagai "test".

Contoh sederhana: bayangkan Anda tidak membedakan warna, dan orang lain - pepatah - mengklaim bahwa dua bola memiliki warna yang berbeda. Anda tidak dapat memverifikasi pernyataan ini sendiri, tetapi melalui interogasi yang cerdik, Anda masih dapat memverifikasi bahwa itu benar.

Letakkan bola di belakang dan campur. Mintalah pepatah untuk memberi tahu Anda warna yang mana. Jika mereka benar-benar berbeda warna, peribahasa harus terus-menerus menjawab pertanyaan dengan benar. Jika mereka memiliki warna yang sama - yaitu, mereka terlihat sama - pepatah dalam setengah kasus akan mengungkapkan tebakan yang salah.

"Jika saya melihat bahwa Anda telah mencapai lebih banyak keberhasilan daripada dalam separuh kasus, maka saya akan hampir yakin bahwa warnanya tidak sama," kata Vidik.

Dengan mengajukan pertanyaan yang tepat, Anda dapat mengkonfirmasi kebenaran solusi untuk berbagai tugas yang lebih besar daripada yang bisa Anda selesaikan sendiri.

Pada tahun 1988, para ilmuwan komputer memikirkan apa yang akan terjadi jika dua prover menyarankan solusi untuk masalah yang sama. Lagipula, jika Anda memiliki kesempatan untuk menginterogasi dua tersangka, akan lebih mudah bagi Anda untuk menyelesaikan kejahatan atau mengkonfirmasi kebenaran keputusan - mereka dapat dibandingkan satu sama lain.

“Bagi mereka yang memeriksanya, itu memberi lebih banyak ruang untuk tekanan. Anda menginterogasi, mengajukan pertanyaan terkait kasus ini, memeriksa ulang jawabannya, ”kata Vidik. Jika para tersangka mengatakan yang sebenarnya, jawaban mereka seharusnya hampir bersamaan. Jika mereka berbohong, akan ada lebih banyak kontradiksi.

Demikian pula, para peneliti menunjukkan bahwa dengan menginterogasi secara terpisah kedua prover mengenai jawaban mereka, orang dapat dengan cepat mengkonfirmasi kebenaran solusi untuk kelas masalah yang lebih luas, dibandingkan dengan yang Anda dapat dekati dengan hanya satu prover.

Kompleksitas komputasi bagi Anda tampaknya merupakan gagasan yang murni teoretis, tetapi bagaimanapun juga erat kaitannya dengan dunia nyata. Sumber daya yang dibutuhkan komputer untuk menyelesaikan masalah dan mengkonfirmasi keputusan - waktu dan memori - pada dasarnya bersifat fisik. Oleh karena itu, penemuan baru dalam fisika dapat mengubah kompleksitas komputasi.

"Jika Anda memilih serangkaian hukum fisika yang berbeda, misalnya, dunia kuantum alih-alih yang klasik, maka teori kompleksitas lain dapat disimpulkan darinya," kata Natarajan.

Bukti baru adalah hasil akhir dari konfrontasi antara ilmuwan komputer abad ke-21 dan salah satu ide aneh fisika abad ke-20: keterjeratan.

Hipotesis sarang Conn

Ketika dua partikel terjerat, mereka tidak saling mempengaruhi - mereka tidak memiliki hubungan sebab akibat. Einstein et al. Mengungkapkan ide ini dalam makalah 1935. Setelah itu, fisikawan dan ahli matematika mencoba menemukan cara matematika untuk menggambarkan apa arti kebingungan sebenarnya.

Namun, ada beberapa kebingungan. Ilmuwan datang dengan dua model matematis keterjeratan yang berbeda - dan fakta bahwa mereka setara satu sama lain sama sekali tidak jelas.

Secara tidak langsung, disonansi potensial ini memengaruhi munculnya masalah penting dari bidang matematika murni, hipotesis Conn of Nesting. Dan pada akhirnya, itu juga berfungsi sebagai perpecahan, yang dimanfaatkan oleh lima ilmuwan komputer dalam bukti baru mereka.

Cara pertama untuk memodelkan keterjeratan adalah membayangkan partikel yang terisolasi secara spasial. Salah satunya, misalnya, ada di Bumi, dan yang lain ada di Mars; jarak di antara mereka tidak termasuk hubungan sebab akibat. Ini disebut model produk tensor.

Tetapi dalam beberapa situasi, tidak sepenuhnya jelas apakah dua objek benar-benar terisolasi satu sama lain. Oleh karena itu, ahli matematika telah menemukan cara yang lebih umum untuk menggambarkan independensi kausal.

Ketika urutan operasi pada objek tidak menjadi masalah, operasi dianggap beralih: 3 x 2 akan memberikan yang sama dengan 2 x 3. Dalam model kedua, partikel terjerat ketika sifat-sifatnya berkorelasi, tetapi urutan pengukuran tidak masalah. Ukur partikel A untuk memprediksi momentum partikel B, atau sebaliknya. Bagaimanapun, jawabannya akan sama. Ini disebut model keterlibatan operator yang diaktifkan.

Kedua deskripsi keterjeratan menggunakan array angka yang disusun dalam kolom dan baris - matriks. Model produk tensor menggunakan matriks dengan jumlah kolom dan baris yang terbatas. Model keterikatan operator pergantian menggunakan objek yang lebih umum yang bekerja seperti matriks tetapi memiliki jumlah baris dan kolom yang tak terbatas.

Seiring waktu, matematikawan mulai mengeksplorasi matriks ini sendiri, secara terpisah dari hubungan mereka dengan fisika. Dalam kerangka kerja ini, matematikawan Alain Conn pada tahun 1976 berhipotesis bahwa banyak matriks dimensi tak terbatas dapat didekati oleh matriks dengan dimensi terbatas. Ini adalah salah satu kesimpulan hipotesis bersarang Conn.

Pada dekade berikutnya, fisikawan Soviet [dalam fisika asli, tetapi di Wikipedia terdaftar sebagai ahli matematika / kira-kira. terjemahan.] Boris Tsirelson mengusulkan versinya sendiri tentang masalah ini, yang lagi-lagi dikaitkan dengan fisika. Zirelson menyarankan bahwa produk tensor dan model operator komutatif yang menggambarkan keterjeratan kira-kira setara. Ini masuk akal, karena secara teoritis ini adalah dua cara berbeda untuk menggambarkan fenomena fisik yang sama. Karya-karya berikutnya menunjukkan bahwa, karena koneksi dari matriks dan model fisik yang menggunakannya, hipotesis Conn tentang bersarang dan masalah Zirelson saling mengikuti: pecahkan satu dan pecahkan lainnya.

Namun, solusi untuk kedua masalah tersebut muncul dalam arah yang sama sekali berbeda.

Fisika dan permainan

Pada 1960-an, fisikawan John Bell datang dengan tes untuk menentukan apakah keterikatan adalah fenomena fisik yang nyata atau hanya ide teoretis. Sesuatu seperti permainan ikut serta dalam pengujian, yang hasilnya melaporkan apakah sesuatu selain fisika biasa, non-kuantum berperan dalam percobaan.

Nantinya, ilmuwan komputer akan menyadari bahwa tes keterikatan ini juga dapat digunakan sebagai alat untuk memvalidasi solusi untuk masalah yang sangat kompleks.

Tapi pertama-tama, untuk memahami cara kerja gim ini, bayangkan dua pemain, Alice dan Bob, dan sebuah kotak 3x3. Juri memberi Alice sebuah garis dan menyarankan bahwa dia menaruh 0 atau 1 garis di setiap sel sehingga jumlah angka itu ganjil. Bob diberi kolom, dan ia harus mengisi semua selnya sehingga jumlah angkanya genap. Mereka menang jika mereka memasukkan nomor yang sama di sel yang sama - di mana baris dan kolom yang dipilih bersilangan. Tetapi pada saat yang sama mereka tidak dapat berkomunikasi.

Dalam kondisi normal, yang terbaik yang bisa dilakukan pemain adalah menang dalam 89% kasus. Tetapi di dunia kuantum, mereka dapat meningkatkan hasil ini.

Misalkan Alice dan Bob berbagi sepasang partikel terjerat. Masing-masing dari mereka melakukan pengukuran partikelnya dan menggunakan hasilnya untuk menentukan apakah akan menulis 0 atau 1. Di setiap sel, karena partikel-partikel terjerat, hasil pengukurannya akan berkorelasi satu sama lain, yang berarti bahwa jawaban mereka juga akan berkorelasi - yang berarti , mereka akan dapat menang dalam 100% kasus.

Jadi jika Anda melihat bahwa dua pemain sering memenangkan permainan secara tidak terduga, Anda dapat menyimpulkan bahwa mereka menggunakan sesuatu di luar fisika klasik. Sekarang eksperimen Bell disebut permainan "non-lokal", mengacu pada pemisahan pemain. Dan fisikawan sebenarnya melakukan percobaan seperti itu di laboratorium.

"Orang-orang telah melakukan percobaan seperti itu selama bertahun-tahun, dan itu mengikuti dari mereka bahwa efek menakutkan ini benar-benar ada," kata Ewan.

Saat menganalisis permainan apa pun, Anda mungkin perlu informasi tentang seberapa sering pemain memenangkan permainan non-lokal jika mereka mencoba bermain dengan cara terbaik. Misalnya, jika Anda menggunakan Solitaire Solitaire, maka Anda dapat menghitung probabilitas yang dapat dimainkan oleh pemain yang bermain sempurna.

Tetapi pada tahun 2016, William Slofstra membuktikan bahwa tidak ada algoritma umum untuk menghitung probabilitas maksimum yang tepat untuk menang di permainan non-lokal. Para peneliti mengajukan pertanyaan: apakah mungkin untuk setidaknya memperkirakan secara kasar persentase kemenangan maksimum?

Ilmuwan komputer mencari jawaban menggunakan dua model yang menggambarkan seluk-beluk. Algoritma yang menggunakan model produk tensor menentukan batas bawah, atau nilai minimum dari perkiraan probabilitas maksimum untuk memenangkan semua game non-lokal. Algoritme lain yang menggunakan model keterjeratan dengan operator dial-up menentukan batas atasnya.

Semakin lama algoritma ini bekerja, semakin akurat hasil yang mereka hasilkan. Jika prediksi Zirelson benar, dan kedua model ini benar-benar setara, maka batas bawah dan batas atas secara bertahap akan semakin dekat, konvergen ke nilai tunggal dari perkiraan probabilitas maksimum untuk menang.

Tetapi jika prediksi Cirelson salah, dan kedua model itu tidak setara, "batas bawah dan atas selamanya akan tetap terpisah," kata Ewan. Tidak mungkin untuk menghitung bahkan nilai perkiraan probabilitas maksimum untuk menang untuk permainan non-lokal.

Dalam karya baru, lima peneliti menggunakan topik ini - apakah batas bawah dan atas bertemu, dan apakah hipotesis Tsirelson benar - untuk memecahkan pertanyaan terpisah tentang kemungkinan mengkonfirmasi kebenaran solusi dari masalah komputasi.

Bantuan rumit

Pada awal 2000-an, para ilmuwan komputer berpikir: bagaimana berbagai tugas akan berubah, solusinya dapat dikonfirmasi dengan mewawancarai dua prover dengan partikel rumit?

Sebagian besar memutuskan bahwa keterikatan akan bermain melawan konfirmasi. Memang, akan lebih mudah bagi dua tersangka untuk membangun kebohongan yang konsisten jika mereka memiliki cara untuk mengoordinasikan jawaban.

Tetapi dalam beberapa tahun terakhir, para ilmuwan komputer telah menyadari bahwa itu sebenarnya sebaliknya: dengan menginterogasi prover, membagi pasangan partikel terjerat, orang dapat mengkonfirmasi solusi untuk masalah yang jauh lebih luas daripada tanpa terjerat.

"Kebingungan adalah salah satu cara untuk mendapatkan korelasi yang tampaknya membantu mereka berbohong dan menipu," kata Vidik. "Tapi kamu benar-benar bisa membungkusnya untuk kebaikanmu."

Untuk memahami bagaimana ini mungkin, pertama-tama Anda perlu mengevaluasi berbagai tugas yang hampir supranatural yang solusinya dapat Anda periksa dengan prosedur interaktif ini.

Bayangkan sebuah grafik - sekumpulan titik (simpul) yang dihubungkan oleh garis (tepi). Anda mungkin ingin mencari tahu apakah mungkin untuk mewarnai simpul dengan tiga warna sehingga tidak ada pasangan simpul dengan warna yang sama, disatukan oleh tepi yang sama.

Jika Anda memberi beberapa orang membuktikan grafik yang sangat besar, dan mereka mengatakan itu dapat diwarnai dalam tiga warna seperti yang dijelaskan, Anda akan berpikir: apakah ada cara untuk memeriksa jawaban ini?

Grafik yang sangat besar tidak dapat diverifikasi secara langsung. Sebagai gantinya, Anda dapat meminta setiap prover untuk melaporkan warna dua simpul yang terhubung oleh suatu sisi. Jika mereka melaporkan warna yang berbeda, dan setiap kali memberikan warna yang berbeda selama survei tentang simpul lain, kepercayaan diri Anda bahwa melukis dengan tiga warna berhasil akan tumbuh.

Tetapi strategi pemungutan suara seperti itu juga berhenti bekerja ketika grafik menjadi sangat besar - ketika jumlah tepi dan simpul mulai melebihi jumlah atom di Semesta. Untuk verifikasi, bahkan tugas seperti mengajukan pertanyaan tertentu ("beri tahu saya warna XYZ vertex") menjadi tak tertahankan - jumlah data yang diperlukan untuk menamai titik tertentu melebihi memori kerja yang tersedia untuk itu.

Namun, kebingungan membuat orang prover mengajukan pertanyaan sendiri.

“Peninjau tidak perlu mencari tahu pertanyaannya. Inspektur membuat prover sendiri menghitung pertanyaan untuknya, ”kata Wright.

Inspektur perlu prover untuk memberitahunya warna dari simpul yang terhubung. Jika simpul tidak terhubung, maka jawaban atas pertanyaan tidak akan mengatakan apa pun tentang kemungkinan mewarnai grafik dalam tiga warna. Dengan kata lain, pemeriksa ingin pepatah untuk menanyakan pertanyaan terkait: satu pepatah menanyakan pertanyaan tentang vertex ABC, dan yang lain tentang vertex XYZ. Dan saya ingin kedua puncak ini terhubung, meskipun tidak satu pun dari prover yang tahu puncak mana yang dibicarakan. Dengan cara yang sama seperti Alice dan Bob berharap untuk menempatkan nomor yang sama di kotak yang sama, meskipun tidak ada dari mereka yang tahu baris dan kolom mana yang digunakan.

Jika masing-masing dari dua prover akan mengeluarkan pertanyaan sepenuhnya pada mereka sendiri, mereka tidak dapat dipaksa untuk memilih terhubung, atau menghubungkan, puncak, sehingga pemeriksa dapat mengkonfirmasi jawaban mereka. Namun, keterjeratan hanya memungkinkan Anda untuk membangun korelasi.

“Kami akan menggunakan kebingungan untuk membuang semua pekerjaan pada prover. Kami akan membuat mereka memilih pertanyaan mereka sendiri, ”kata Vidik.

Di akhir prosedur, masing-masing prover melaporkan warna. Peninjau memeriksa mereka untuk kecocokan. Jika grafik sebenarnya bisa diwarnai dalam tiga warna, prover seharusnya tidak pernah menghasilkan warna yang sama.

"Jika penghitungan dapat dilukis dalam tiga warna, prover dapat meyakinkan Anda tentang ini," kata Ewan.

Ternyata prosedur konfirmasi ini adalah contoh lain dari game non-lokal. Prover “menang” dengan meyakinkan Anda tentang kebenaran keputusan mereka.

Pada 2012, Vidik dan Tsiyoshi Ito membuktikan bahwa dimungkinkan, dengan memainkan berbagai permainan non-lokal dengan bukti yang membingungkan, untuk mengonfirmasi jawaban atas setidaknya jumlah tugas yang sama seperti ketika menginterogasi dua komputer klasik. Artinya, penggunaan provers yang membingungkan tidak merusak konfirmasi ottetes mereka. Dan tahun lalu, Natarajan dan Wright membuktikan bahwa berinteraksi dengan prover berbelit-belit sebenarnya memperluas kelas tugas yang divalidasi.

Namun, untuk titik ini, para ilmuwan komputer belum dapat menebak ukuran dari berbagai tugas, solusinya dapat dikonfirmasi dengan cara yang sama.

Kaskade konsekuensi

Dalam karya baru ini, lima ilmuwan komputer membuktikan bahwa interogasi terhadap provol yang berbelit-belit dapat mengkonfirmasi solusi untuk masalah yang belum terselesaikan, termasuk masalah berhenti.

"Kemampuan validasi model ini luar biasa," kata Ewan.

Namun, masalah berhenti tidak bisa diselesaikan. Dan fakta ini menjadi kunci untuk melengkapi buktinya.

Misalkan Anda memberikan program kepada beberapa prover yang membingungkan. Anda meminta mereka untuk mengatakan apakah eksekusi akan berhenti. Anda siap menguji jawaban mereka melalui berbagai permainan non-lokal: pemain pro memberikan pertanyaan dan menang tergantung pada konsistensi jawaban mereka.

Jika program benar-benar berhenti, prover harus dapat memenangkan permainan ini dalam 100% kasus - seperti dalam kasus grafik yang dapat diwarnai dengan tiga warna, ketika prover yang berbelit-belit tidak harus memberikan warna yang sama untuk dua simpul yang terhubung. Jika program tidak berhenti, maka prover hanya akan menang secara kebetulan - yaitu, dalam 50% kasus.

Ini berarti bahwa jika seseorang meminta Anda untuk menentukan perkiraan probabilitas maksimum untuk menang untuk permainan non-lokal tertentu, Anda harus terlebih dahulu menyelesaikan masalah berhenti. Tetapi tidak mungkin dipecahkan. Yang berarti bahwa tugas menghitung perkiraan probabilitas maksimum untuk menang tidak dapat diselesaikan, seperti halnya masalah penghentian.

Dan ini, pada gilirannya, berarti bahwa jawaban untuk masalah Zirelson negatif - dua model keterjeratan tidak setara. Jika ya, akan mungkin untuk mengurangi batas bawah dan atas skor bersama-sama dan menghitung perkiraan probabilitas maksimum untuk menang.

"Tidak mungkin ada algoritma seperti itu, sehingga kedua model harus berbeda," kata David Perez-Garcia dari Complutense University of Madrid.

Karya baru membuktikan bahwa kelas masalah yang solusinya dapat dikonfirmasi dengan berinteraksi dengan pembalik kuantum terjerat, MIP *, benar-benar setara dengan kelas masalah yang tidak lebih rumit daripada masalah berhenti, RE. Judul karya secara singkat menjelaskan esensinya: "MIP * = RE".

Dalam proses mencari bukti kesetaraan dua kelas kompleksitas, ilmuwan komputer membuktikan kepalsuan hipotesis Tsirelson, yang, berkat karya sebelumnya, berarti kepalsuan hipotesis Conn tentang bersarang.

Itu mengejutkan bagi para peneliti dari bidang yang relevan bahwa jawaban untuk masalah yang kompleks tersebut diidentifikasi dalam proses bukti yang tampaknya tidak terkait dari bidang ilmu komputer.

"Setelah melihat sebuah karya yang disebut MIP * = RE, saya pasti tidak akan berpikir bahwa itu ada hubungannya dengan pekerjaan saya," kata Navazquez, rekan penulis dari karya sebelumnya yang menghubungkan hipotesis Cirelson dengan hipotesis Conn tentang bersarang. "Itu benar-benar kejutan bagiku."

Spesialis dalam fisika kuantum dan matematika baru mulai mencerna informasi ini. Sebelumnya, matematikawan tertarik pada apakah mereka dapat memperkirakan matriks dimensi tak terbatas dengan yang terbatas. Sekarang, mengetahui kepalsuan hipotesis bersarang Conn, mereka tahu bahwa mereka tidak bisa.

"Dari hasil mereka, itu tidak mungkin," kata Slofstra.

Ilmuwan komputer sendiri tidak mencoba menemukan konfirmasi hipotesis Conn tentang bersarang, sehingga orang lain harus menjelaskan semua konsekuensi dari jawaban yang mereka temukan.

“Saya sendiri bukan ahli matematika. Saya tidak mengerti dengan baik definisi awal hipotesis Conn tentang bersarang, ”kata Natarajan.

Mereka dan rekan penulis menyarankan bahwa matematikawan sendiri akan menerjemahkan hasil baru ke dalam bahasa bidang mereka. Dalam sebuah artikel yang menyatakan bukti, Vidik menulis: "Saya tidak ragu bahwa teori kompleksitas tidak lagi diperlukan untuk mendapatkan hasil matematika murni."

Bukti yang dihasilkan mengganggu rantai panjang penelitian yang mengarah ke sana. Selama lebih dari tiga dekade, para ilmuwan komputer telah berusaha mencari tahu sejauh mana konfirmasi interaktif mereka akan mengarah. Sekarang mereka memiliki jawaban dalam bentuk karya panjang dengan judul sederhana dan referensi ke Turing.

“Ada daftar pekerjaan yang agak besar yang bertanya tentang peluang apa yang mungkin ada” dalam prosedur konfirmasi dengan bantuan dua pemicu yang membingungkan, kata Natarajan. “Sekarang kita tahu yang mana. Ceritanya sudah berakhir. "

Bukti signifikan dari teorema pada ilmu komputer menangkap fisika dengan matematika