🧙🏻 🤱🏾 👩🏾‍🎨 MIP * = RE: bukti pembuatan zaman dari bidang ilmu komputer yang menyebabkan efek domino dalam fisika dan matematika ▫️ 🕛 🧖🏻

Ilmuwan komputer telah mencapai batas baru dalam verifikasi solusi untuk masalah dengan metode komputasi. Pada saat yang sama, mereka menemukan jawaban atas pertanyaan terbuka terpenting mekanika kuantum dan matematika murni.

Pada tahun 1935, Albert Einstein, bekerja dengan Boris Podolsky dan Nathan Rosen, menyelidiki kemungkinan yang dibuka oleh hukum fisika kuantum yang baru: dua partikel dapat berada dalam keadaan terjerat ketika bahkan jarak yang sangat jauh tidak melanggar interkoneksi mereka. Tahun berikutnya, Alan Turing merumuskan teori komputasi umum pertama, dan membuktikan bahwa ada masalah yang tidak pernah bisa dipecahkan oleh komputer. Kedua ide ini merevolusi bidang ilmu yang mereka hubungkan. Selain itu, sepertinya mereka tidak ada hubungannya satu sama lain. Tapi sekarang buktinya

MIP * = RE menggabungkan mereka, yang mengarah ke solusi dari banyak masalah di bidang ilmu komputer, fisika dan matematika.

Komputer kuantum melakukan perhitungan menggunakan bit kuantum terjerat (qubit), bukan nol dan klasik. Bukti baru menunjukkan bahwa komputer semacam itu, secara teoritis, dapat digunakan untuk menguji solusi untuk sejumlah besar masalah. Hubungan antara keterikatan kuantum dan komputasi tradisional adalah kejutan besar bagi banyak peneliti.

Miguel Navascués adalah mahasiswa fisika kuantum di Institute of Quantum Optics dan Quantum Information di Wina. "Itu benar-benar kejutan," katanya, mengomentari bukti.

Rekan penulis dari bukti menetapkan tujuan mendefinisikan batas-batas pendekatan untuk memverifikasi solusi untuk masalah komputasi. Pendekatan ini melibatkan keterikatan kuantum. Setelah menemukan batas-batas ini, para peneliti menemukan solusi dari dua masalah lain, yang hampir merupakan produk sampingan dari pekerjaan mereka. Kita berbicara tentang hipotesis Zirelson dalam fisika mengenai pemodelan matematis keterikatan kuantum dan masalah terkait dalam matematika murni - masalah Conn dalam teori aljabar von Neumann (masalah penanaman Conn).

Akibatnya, hasil menerapkan bukti dalam matematika dan fisika menyebabkan sesuatu seperti efek domino.

“Semua ide milik periode yang sama. Sangat menyenangkan melihat mereka berkumpul lagi dengan cara yang spektakuler, ”kata Henry Yuen) dari University of Toronto - salah satu penulis bukti. Selain dia dalam pekerjaan ini berpartisipasi Chzhenfen Ji ( Zhengfeng dari Ji ) dari University of Technology Sydney, John Wright ( the John Wright ) dari University of Texas di Austin, Anand Natarajan ( Anand Natarajan ) dan Thomas Vidic ( oleh Thomas Vidick ) dari Institut Teknologi California. Kelima ilmuwan bekerja di bidang ilmu komputer.

Masalah yang tak terpecahkan

Turing, bahkan sebelum munculnya komputer, meletakkan fondasi di mana refleksi pada komputasi dibangun. Dan dia, pada saat yang sama, menunjukkan bahwa ada masalah tertentu yang, yang dapat dibuktikan, tidak dapat diselesaikan oleh komputer. Inilah yang disebut masalah shutdown.

Biasanya, program komputer menerima sesuatu pada input dan menghasilkan output. Tetapi kadang-kadang mereka terjebak dalam siklus tanpa akhir, yang berarti mereka tidak pernah berhenti. Ketika ini terjadi, hanya ada satu jalan keluar dari situasi ini. Menurut Henry Yuen, Anda harus menghentikan program secara manual. Anda hanya perlu mengakhiri pekerjaannya.

Turing membuktikan bahwa tidak ada algoritma universal yang dapat menentukan apakah suatu program akan dihentikan. Untuk mengetahuinya, Anda perlu menjalankan program.

Henry Yuen, Thomas Widick, Zhengfeng Ji, Anand Natarajan, John Wright

“Anda menunggu sejuta tahun, dan program itu tidak berhenti. Mungkin Anda hanya harus menunggu 2 juta tahun? Tidak ada cara untuk mengatakannya terlebih dahulu, "- kata William Slofstra ( William Slofstra ), ahli matematika dari Universitas Waterloo.

Turing, dari sudut pandang teknis, membuktikan bahwa masalah penutupan tidak dapat dipecahkan. Bahkan komputer paling kuat yang dapat Anda bayangkan tidak mampu mengatasinya.

Setelah Turing, para ilmuwan komputer mulai mengklasifikasikan tugas-tugas lain berdasarkan kompleksitasnya. Tugas yang lebih kompleks membutuhkan lebih banyak daya pemrosesan - lebih banyak waktu dan memori prosesor. Ini adalah studi tentang kompleksitas komputasi algoritma.

Akibatnya, setiap masalah menimbulkan dua pertanyaan besar bagi para peneliti: “Seberapa sulit untuk menyelesaikannya? Apa kesulitan memverifikasi bahwa solusi yang dihasilkan benar? "

Interogasi keputusan melalui interogasi

Jika tugasnya relatif sederhana - solusinya dapat diperiksa secara independen. Tetapi ketika tugas menjadi lebih rumit, bahkan memeriksa hasil dari solusi mereka bisa sangat sulit. Meskipun demikian, pada tahun 1985, para ilmuwan komputer memutuskan bahwa adalah mungkin untuk membangun kepercayaan pada kebenaran jawaban bahkan jika itu tidak mungkin untuk mengkonfirmasi ini sendiri.

Metode verifikasi mengikuti logika interogasi polisi.

Jika tersangka menceritakan kisah yang dipikirkan dengan hati-hati, maka penyidik mungkin tidak akan dapat mengambil dan menemukan konfirmasi dari masing-masing rinciannya. Tetapi dengan mengajukan pertanyaan yang tepat, Anda bisa menangkap tersangka berbohong, atau mengkonfirmasi kebenaran ceritanya.

Dalam hal ilmu komputer, kedua sisi interogasi diwakili oleh dua komputer. Yang pertama adalah sistem komputasi yang kuat yang menawarkan solusi untuk masalah tersebut. Dia disebut saksi. Yang kedua bukan lagi alat yang ampuh yang menanyakan pertanyaan pada penguji untuk menentukan apakah jawaban yang ia tawarkan sudah benar. Komputer ini disebut verifier.

Pertimbangkan contoh sederhana. Misalkan seseorang (pemeriksa) menderita buta warna. Orang lain (saksi) mengklaim bahwa kedua bola dicat dengan warna yang berbeda dan tidak berbeda satu sama lain. Verifier tidak dapat memverifikasi pernyataan ini sendiri. Tapi, setelah membangun interogasi dengan cerdas, dia masih bisa mengetahui apakah ini benar-benar terjadi.

Untuk melakukan ini, Anda bisa menyembunyikan bola di belakang dan mencampurnya. Dan kemudian - tanyakan pepatah tentang bola mana yang ada di tangan mana. Jika mereka benar-benar berbeda, pepatah harus selalu menjawab pertanyaan seperti itu dengan benar. Tetapi jika mereka memiliki warna yang sama, yaitu, mereka terlihat persis sama, setengah jawaban dari peribahasa itu ternyata salah.

Thomas Widick mengatakan bahwa jika jauh lebih dari separuh jawaban peribahasa ternyata benar, maka orang dapat sangat yakin bahwa bola memiliki warna yang berbeda.

Dengan mengajukan pertanyaan yang tepat, Anda dapat memverifikasi solusi dari kelas masalah yang lebih luas daripada yang dapat Anda verifikasi sendiri.

Pada tahun 1988, ilmuwan komputer meneliti situasi di mana ada dua prover yang menawarkan solusi untuk masalah yang sama. Pada akhirnya, jika ada dua tersangka yang dapat diinterogasi, ini akan menyederhanakan pengungkapan kejahatan, atau - verifikasi keputusan, karena mereka dapat dipaksa untuk bermain melawan satu sama lain.

Menurut Thomas Widick, ini memberi verifier lebih banyak pengaruh. Dia menginterogasi, mengajukan pertanyaan terkait, memeriksa ulang jawabannya. Jika tersangka mengatakan yang sebenarnya, sebagian besar jawaban mereka harus cocok satu sama lain. Jika mereka berbohong, jawaban mereka akan sering berbeda.

Demikian pula, para peneliti menunjukkan bahwa dengan menginterogasi dua saksi secara terpisah, mengajukan pertanyaan kepada mereka tentang solusi yang mereka temukan, dimungkinkan untuk dengan cepat memverifikasi solusi dari kelas masalah yang bahkan lebih luas daripada ketika mereka bekerja dengan satu prover.

Studi tentang kompleksitas komputasi dari algoritma mungkin tampak murni teoretis, tetapi mereka sangat terkait erat dengan dunia nyata. Sumber daya yang dibutuhkan komputer untuk menyelesaikan masalah dan memverifikasi solusi - waktu dan memori - adalah sumber daya fisik. Untuk alasan ini, penemuan baru dalam fisika dapat mengubah pendekatan untuk mempelajari kompleksitas komputasi.

Anand Natarajan mengatakan bahwa jika kita menjauh dari basis fisik klasik komputasi dan memilih sesuatu yang sama sekali berbeda, seperti mekanisme kuantum, maka kita juga akan mendapatkan teori baru kompleksitas komputasi.

Bukti baru adalah hasil akhir dari tabrakan ilmuwan komputer abad ke-21 dengan salah satu ide aneh fisika abad terakhir - dengan gagasan keterikatan kuantum.

Masalah Conn

Ketika dua partikel terjerat, mereka, pada kenyataannya, tidak saling mempengaruhi. Tidak ada hubungan kausal antara tindakan mereka. Einstein dan rekan penulisnya mengerjakan ide ini dalam sebuah artikel tahun 1935. Selanjutnya, fisikawan dan matematikawan mencoba untuk sampai pada cara matematika untuk menggambarkan apa sebenarnya keterjeratan kuantum.

Namun, upaya ini membuahkan hasil yang beragam. Para ilmuwan telah menemukan dua model keterjeratan matematika yang berbeda. Namun, tidak jelas apakah model ini setara satu sama lain.

Kehadiran disonansi potensial seperti itu, secara tidak langsung, menyebabkan munculnya masalah penting di bidang matematika murni. Ini adalah masalah Conn dalam teori aljabar von Neumann. Pada akhirnya, itu memainkan peran semacam "petunjuk" bahwa lima ilmuwan komputer mengambil keuntungan dari penurunan bukti mereka.

Cara pertama untuk memodelkan keterikatan kuantum adalah dengan memahami partikel sebagai objek yang terisolasi secara spasial satu sama lain. Misalkan salah satu partikel ini ada di Bumi, dan yang lain ada di Mars. Jarak di antara mereka adalah sesuatu yang mengecualikan hubungan sebab akibat di antara mereka (mereka dipisahkan secara kausal). Inilah yang disebut model produk tensor.

Tetapi dalam beberapa situasi, pemisahan sebab akibat dari entitas tidak sepenuhnya jelas. Akibatnya, ahli matematika tiba pada cara kedua, yang lebih umum untuk menggambarkan independensi kausal.

Ketika urutan dua operasi dilakukan tidak mempengaruhi hasil, operasi disebut komutatif: 3x2 sama dengan 2x3. Dalam model kedua ini, partikel terjerat ketika sifat-sifatnya berkorelasi, tetapi urutan pengukuran tidak menjadi masalah. Seseorang dapat melakukan pengukuran pada partikel A untuk memprediksi momentum partikel B, dan sebaliknya. Bagaimanapun, hasilnya akan sama. Ini disebut model keterjeratan operator pergantian.

Kedua deskripsi keterjeratan menggunakan array angka yang disebut matriks. Matriks terdiri dari baris dan kolom. Model produk tensor menggunakan matriks dengan jumlah baris dan kolom yang terbatas. Model operator pergantian menggunakan objek yang lebih umum yang berfungsi sebagai matriks dengan jumlah baris dan kolom yang tak terbatas.

Seiring berjalannya waktu, matematikawan mulai mempelajari matriks-matriks ini sebagai objek yang memiliki minat independen, yang tidak terhubung dengan dunia fisik. Sejalan dengan pekerjaan ini, matematikawan Alain Connes menyarankan pada tahun 1976 bahwa mungkin untuk memperkirakan banyak matriks dari dimensi tak terbatas dengan menggunakan matriks dimensi hingga. Ini adalah salah satu konsekuensi dari masalah Conn dalam teori von Neumann algebras.

Pada dekade berikutnya, fisikawan Boris Tsirelson merumuskan versi baru dari masalah ini, yang kembali mengembalikannya ke bidang fisika. Zirelson menyarankan bahwa model produk tensor dan operator komuter kira-kira setara satu sama lain. Pernyataan ini masuk akal, karena kedua model ini, secara teoritis, adalah dua cara berbeda untuk menggambarkan fenomena fisik yang sama. Pekerjaan selanjutnya menunjukkan bahwa karena hubungan antara matriks dan model fisik yang menggunakannya, masalah Conn dan Zirelson secara tidak langsung terkait: jika satu dipecahkan, yang lain akan dipecahkan.

Tetapi solusi untuk kedua masalah ini datang dari tempat yang sama sekali tidak terduga.

Fisika permainan

Pada 1960-an, fisikawan John Bell datang dengan tes untuk menentukan apakah keterikatan kuantum adalah fenomena fisik yang nyata, bukan konsep teoretis. Tes ini menggunakan sesuatu seperti permainan, yang hasilnya memungkinkan untuk mengetahui apakah mekanisme tertentu yang tidak terkait dengan pekerjaan fisika biasa selama permainan.

Kemudian, para ilmuwan komputer menyadari bahwa tes ini terkait dengan keterikatan kuantum juga dapat digunakan sebagai alat untuk memverifikasi solusi untuk masalah yang sangat kompleks.

Tetapi sebelum melanjutkan, mari kita bicara tentang permainan. Bayangkan ada dua pemain: Alice dan Bob, dan juga lapangan bermain 3x3. Presenter memberikan garis pada Alice dan memintanya untuk memasukkan 0 atau 1 di setiap sel, sehingga jumlah mereka akan memberikan angka ganjil. Bob mendapat kolom yang harus diisi dengan angka nol dan satu sehingga jumlah mereka akan memberikan angka genap. Mereka akan menang jika mereka meletakkan nomor yang sama di tempat baris dan kolom bersilangan. Mustahil untuk berkomunikasi dengannya.

Dalam keadaan biasa, yang terbaik yang bisa mereka lakukan adalah memenangkan 89% dari waktu. Tetapi jika Anda memperhitungkan faktor keterikatan kuantum, maka peluang mereka akan meningkat.

Bayangkan bahwa Alice dan Bob telah menjerat partikel kuantum. Mereka mengambil pengukuran partikel mereka dan menggunakan hasil pengukuran untuk menunjukkan apa yang harus ditulis dalam setiap sel - 0 atau 1. Karena partikel terjerat, hasil pengukuran akan berkorelasi satu sama lain. Dan ini juga berarti bahwa tindakan para pemain akan saling berhubungan. Hasilnya, ternyata mereka akan selalu bisa memenangkan permainan.

Jika ada nomor yang berbeda di sel tempat baris dan kolom bersilangan, permainan hilang. Jika mereka sama - menang

, maka, jika ternyata dua pemain secara mengejutkan berhasil dalam memainkan permainan ini, maka kita dapat menyimpulkan bahwa mereka menggunakan sesuatu yang berbeda dari apa yang dapat diberikan oleh fisika klasik. Eksperimen "Bell" ini sekarang disebut permainan "non-lokal", mengacu pada pemisahan pemain. Fisikawan, pada kenyataannya, melakukan permainan serupa di laboratorium.

Henry Yuen mengatakan bahwa selama bertahun-tahun, para ilmuwan telah melakukan percobaan untuk membuktikan kenyataan dari fenomena yang menakutkan ini.

Seperti halnya analisis permainan apa pun, Anda mungkin perlu mencari tahu seberapa sering pemain bisa menang dalam permainan non-lokal, mengingat mereka bermain sebaik mungkin. Misalnya, dalam kasus solitaire, Anda dapat menghitung frekuensi kemungkinan kemenangan dari orang yang bermain sempurna.

Namun pada tahun 2016, William Slofstra membuktikan bahwa tidak ada algoritma umum untuk menghitung probabilitas maksimum yang tepat untuk menang di semua game non-lokal. Akibatnya, para peneliti mengajukan pertanyaan: apakah mungkin untuk setidaknya kira-kira menghitung persentase kemenangan maksimum?

Ilmuwan komputer sampai pada jawabannya menggunakan dua model keterikatan kuantum yang dijelaskan di atas. Algoritme yang menggunakan model produk tensor menetapkan nilai minimum untuk perkiraan perhitungan probabilitas maksimum untuk semua game non-lokal. Algoritma lain yang menggunakan model operator switching menetapkan nilai maksimum.

Jawaban yang diberikan oleh implementasi algoritma ini, semakin akurat, semakin lama program berjalan. Jika hipotesis Zirelson benar, dan kedua model ini setara, maka batas bawah dan atas harus saling mendekati, berubah menjadi nilai tunggal yang mewakili perkiraan probabilitas maksimum untuk menang.

Tetapi jika hipotesis Zirelson tidak benar, dan dua model tidak setara, maka, menurut Henry Yuen, batas atas dan bawah akan selalu dipisahkan. Dan tidak akan ada cara untuk menghitung bahkan perkiraan persentase kemenangan untuk game non-lokal.

Lima peneliti dalam karya baru mereka mengambil keuntungan dari argumen tentang apakah batas atas dan bawah bertemu, dan apakah hipotesis Zirelson benar atau salah. Mereka melakukan ini demi menemukan jawaban atas pertanyaan di mana situasi itu mungkin untuk memverifikasi solusi untuk masalah komputasi.

Bantuan rumit

Pada awal ilmuwan komputer ke dua ribu, mereka mulai bertanya-tanya bagaimana berbagai tugas akan berubah, solusinya dapat diverifikasi dengan "menginterogasi" dua prover yang memiliki partikel rumit.

Sebagian besar ilmuwan berpikir kebingungan membahayakan verifikasi. Pada akhirnya, akan lebih mudah bagi kedua "tersangka" untuk merekonsiliasi kesaksian palsu jika mereka memiliki cara untuk mengoordinasikan tanggapan.

Tetapi selama beberapa tahun berikutnya, menjadi jelas bahwa pernyataan sebaliknya itu benar: dengan "menginterogasi" prover yang memiliki partikel rumit, kelas masalah yang lebih luas dapat diverifikasi daripada ketika bekerja dengan prover yang tidak memiliki partikel seperti itu.

Thomas Widick mengatakan keterjeratan adalah cara menciptakan korelasi yang tampaknya membantu saksi berbohong. Tetapi, faktanya, fenomena ini dapat digunakan untuk keuntungan mereka.

Untuk memahami cara menggunakannya, pertama-tama Anda harus menangani skala tugas yang hampir supranatural yang solusinya dapat diverifikasi berkat prosedur interaktif ini.

Bayangkan sebuah grafik - sekumpulan titik (simpul) yang dihubungkan oleh garis (wajah). Anda perlu mencari tahu apakah, menggunakan tiga warna, dimungkinkan untuk melukis simpul sehingga tidak ada dua simpul dalam grafik yang terhubung oleh wajah dan pada saat yang sama dicat dengan warna yang sama. Jika memungkinkan, maka grafik seperti itu adalah "tiga warna".

Jika Anda memberikan sepasang bukti grafik yang sangat besar, dan mereka mengatakan itu adalah "tiga warna", maka Anda mungkin bertanya-tanya apakah ada cara untuk memverifikasi jawaban mereka.

Dalam kasus grafik yang sangat besar, mustahil untuk memeriksa jawabannya secara langsung. Sebagai gantinya, Anda dapat bertanya kepada masing-masing penguji warna apa yang dimiliki salah satu dari dua simpul yang terhubung. Jika masing-masing dari mereka melaporkan warna yang berbeda, dan mereka akan memberikan jawaban yang sama setiap kali mereka ditanya tentang hal ini, kami akan memiliki keyakinan bahwa grafik tersebut memang "tiga warna".

Tetapi bahkan strategi interogasi ini tidak akan bekerja pada grafik besar dengan lebih banyak wajah dan simpul daripada atom di alam semesta. Bahkan mengajukan pertanyaan tertentu ("Katakan padaku warna titik XYZ") menjadi masalah yang tak tertahankan bagi seseorang yang mencoba memverifikasi solusi untuk suatu masalah. Jumlah data yang diperlukan untuk hanya menentukan nama vertex tertentu lebih besar daripada yang dapat disimpan oleh verifier dalam memori yang tersedia untuknya.

Tetapi keterikatan kuantum memungkinkan skema kerja, dalam aplikasi yang penguji sendiri merumuskan pertanyaan.

“Verifikasi tidak perlu mengajukan pertanyaan. Verifikasi memaksa para pendukung untuk merumuskan secara independen pertanyaan-pertanyaan ini dan menjawabnya, ”kata John Wright.

Verifier memerlukan provers untuk melaporkan warna dari simpul yang terhubung. Jika simpul tidak terhubung, maka jawaban untuk pertanyaan tidak akan mengatakan apa-apa tentang apakah grafik itu "tiga warna" atau tidak. Dengan kata lain, verifikator membutuhkan penguji untuk mengajukan pertanyaan terkait. Salah satu provers bertanya tentang bagian atas ABC, dan yang kedua tentang bagian atas XYZ. Diasumsikan bahwa kedua puncak itu terhubung, meskipun faktanya tidak ada satu pun dari bukti yang tahu mana yang “dipikirkan” oleh yang lain. (Ini mirip dengan bagaimana Alice dan Bob berharap untuk menulis nomor yang sama di sel yang sama, terlepas dari kenyataan bahwa tidak ada dari mereka yang tahu tentang baris atau kolom tabel mana yang bekerja dengan yang lain.)

Jika dua prover akan sepenuhnya merumuskan pertanyaan semacam itu secara independen, maka tidak akan ada mekanisme untuk memaksa mereka untuk memilih simpul yang terhubung (berkorelasi), dengan melakukan sedemikian rupa sehingga memungkinkan verifikasi untuk memverifikasi jawaban mereka. Tetapi korelasi semacam itu adalah persis apa yang dapat dicapai keterikatan kuantum.

Thomas Widick mengatakan mereka akan menggunakan seluk-beluk praktis untuk merujuk semua kasus kepada para saksi. Para ilmuwan membuat para penguji memilih pertanyaan mereka sendiri.

Pada akhir prosedur ini, masing-masing prover melaporkan warna titik. Verifikasi memeriksa apakah warnanya berbeda atau tidak. Jika grafik memang "tri-warna", maka penguji tidak boleh melaporkan warna yang sama.

Menurut Henry Yuen, jika grafiknya adalah "tiga warna," maka para penguji akan dapat meyakinkan peneliti bahwa ini memang benar.

Ternyata, prosedur verifikasi ini adalah contoh lain dari game non-lokal. Proofers “menang” jika mereka meyakinkan peneliti bahwa keputusan mereka benar.

Pada 2012, Thomas Widik dan Tsuyoshi Ito) membuktikan bahwa Anda dapat memainkan berbagai macam permainan non-lokal menggunakan prover berbelit-belit untuk menguji solusi. Ini berlaku, minimal, untuk jumlah tugas yang sama yang dapat diverifikasi dengan menginterogasi dua komputer klasik. Dengan demikian, penggunaan bukti yang membingungkan tidak merusak verifikasi. Tahun lalu, Anand Natarajan dan John Wright membuktikan bahwa berinteraksi dengan saksi mata yang rumit sebenarnya memperluas kelas masalah yang solusinya dapat diverifikasi.

Tetapi para ilmuwan komputer tidak tahu tentang berbagai tugas yang solusinya dapat diverifikasi menggunakan pendekatan ini. Sekarang mereka tahu tentang itu.

efek domino

Dalam karya baru mereka, lima ilmuwan membuktikan bahwa "interogasi" saksi yang kebingungan memungkinkan untuk memverifikasi solusi untuk masalah yang tidak dapat diselesaikan, termasuk solusi dari masalah shutdown.

Henry Yuen mengatakan model jenis ini memiliki kemampuan verifikasi yang tak terbayangkan.

Tetapi tugas penghentian tidak dapat diselesaikan. Dan fakta ini adalah kekuatan pendorong yang mengarah pada bukti akhir.

Bayangkan Anda menyerahkan program itu kepada beberapa saksi yang kebingungan. Anda bertanya kepada mereka apakah program ini akan pernah berhenti. Anda siap memverifikasi jawaban mereka melalui semacam permainan non-lokal. Proofers menghasilkan pertanyaan dan “menang” berdasarkan koordinasi respons mereka.

Jika program benar-benar berhenti, maka para pendukung harus dapat memenangkan permainan dalam 100% kasus. Ini mirip dengan contoh dengan grafik - jika benar-benar "tiga warna", maka prover yang berbelit-belit seharusnya tidak pernah melaporkan warna yang sama untuk simpul yang terhubung. Jika program tidak pernah berhenti, penguji hanya akan menang secara kebetulan - dalam 50% kasus.

Ini berarti bahwa jika seseorang meminta Anda untuk menentukan perkiraan probabilitas maksimum untuk menang untuk permainan non-lokal tertentu, maka Anda harus terlebih dahulu menyelesaikan masalah berhenti. Tetapi untuk memecahkan masalah ini tidak mungkin. Ini berarti bahwa menemukan perkiraan tingkat kemungkinan maksimum untuk menang untuk permainan non-lokal serta untuk masalah berhenti adalah hal yang mustahil.

Dan ini, pada gilirannya, berarti bahwa hipotesis Tsirelson salah: dua model keterikatan kuantum tidak setara. Jika mereka setara, maka akan mungkin untuk mengurangi batas bawah dan atas ke nilai yang sama dan menghitung perkiraan probabilitas maksimum untuk menang.

David Pérez-García dari Complutense University of Madrid mengatakan bahwa algoritma seperti itu tidak dapat ada, akibatnya kedua [model] harus berbeda.

Karya baru membuktikan bahwa kelas masalah yang solusinya dapat diverifikasi dengan bantuan proofer kuantum yang rumit, kelas yang disebut MIP *, persis sama dengan kelas masalah yang tidak lebih rumit daripada masalah berhenti - kelas RE. Judul makalah ini berisi indikasi singkat tentang ini: "MIP * = RE".

Dalam bukti bahwa kedua kelas kompleksitas itu sama, para ilmuwan membuktikan hipotesis Tsirelson salah, yang, berkat penelitian sebelumnya, berarti bahwa hipotesis Conn juga salah.

Para peneliti yang bekerja di bidangnya masing-masing terkejut oleh fakta bahwa solusi untuk masalah berskala besar seperti itu diperoleh berkat bukti dari bidang ilmu komputer, yang, tampaknya, tidak terkait dengan matematika dan fisika.

Miguel Navazquez mengatakan bahwa jika dia melihat artikel dengan judul MIP * = RE, dia tidak akan berpikir bahwa dia memiliki sesuatu yang sama dengan karyanya. Dia adalah rekan penulis dari karya sebelumnya yang menghubungkan hipotesis Zirelson dan Conn. Baginya, ini benar-benar kejutan.

Fisikawan dan ahli matematika kuantum baru saja mulai menguasai bukti baru. Sebelum itu, matematikawan tertarik pada pertanyaan apakah mereka dapat mendekati matriks dimensi tak hingga, menggunakan matriks besar dimensi terbatas sebagai gantinya. Sekarang, berkat fakta bahwa hipotesis Conn telah terbukti salah, mereka tahu bahwa ini tidak dapat dilakukan.

"Hasil mereka menunjukkan bahwa ini tidak mungkin," kata William Slofstra.

Ilmuwan komputer tidak berusaha menganalisis hipotesis Conn. Dan mereka, sebagai akibatnya, tidak dalam posisi terbaik untuk menjelaskan konsekuensi yang mungkin timbul dari penyelesaian masalah ini.

“Secara pribadi, saya bukan ahli matematika. "Saya tidak mengerti betul rumusan awal hipotesis Conn," kata Anand Natarajan.

Dia dan rekan penulisnya berharap ahli matematika menerjemahkan hasil baru ke dalam bahasa mereka sendiri. Dalam sebuah publikasi yang melaporkan buktinya, Thomas Widick menulis: "Saya tidak ragu bahwa pada akhirnya, teori kompleksitas komputasi tidak akan diperlukan untuk mendapatkan hasil yang murni matematis."

Namun demikian, ketika peneliti lain berkenalan dengan buktinya, jalur penelitian, berkat yang memungkinkan untuk mencapainya, berakhir. Selama lebih dari tiga dekade, para ilmuwan komputer hanya mencoba mencari tahu seberapa jauh verifikasi interaktif dari solusi masalah dapat membawa mereka. Sekarang di depan mereka terletak jawabannya, dalam bentuk artikel panjang dengan judul sederhana dan dengan gema dari ide-ide Turing.

“Ada banyak karya yang penulisnya hanya bertanya-tanya apa saja kemungkinan prosedur verifikasi menggunakan dua bukti kuantum yang rumit. Sekarang kita tahu betapa dahsyatnya prosedur ini. Kisah ini telah berakhir, ”kata Anand Natarajan.

Pembaca yang budiman! Apa arti bukti MIP * = RE untuk area di mana Anda bekerja?