Versi aslinya dari cerita ini muncul di Berapa banyak majalah.
Mengajukan pertanyaan kepada bola ajaib 8, dan itu akan menjawab ya, tidak, atau sesuatu yang sangat membingungkan. Kami menganggapnya sebagai mainan anak -anak, tetapi para ilmuwan komputer teoritis menggunakan alat yang sama. Mereka sering membayangkan mereka dapat berkonsultasi dengan perangkat hipotetis yang disebut Oracles yang dapat secara instan, dan dengan benar, menjawab pertanyaan spesifik. Eksperimen pemikiran yang fantastis ini telah menginspirasi algoritma baru dan membantu para peneliti memetakan lanskap perhitungan.
Para peneliti yang meminta Oracles bekerja di subbidang ilmu komputer yang disebut teori kompleksitas komputasi. Mereka prihatin dengan kesulitan yang melekat pada masalah seperti menentukan apakah angka adalah yang utama atau menemukan jalur terpendek antara dua titik dalam suatu jaringan. Beberapa masalah mudah dipecahkan, yang lain tampak jauh lebih sulit tetapi memiliki solusi yang mudah diperiksa, sementara yang lain mudah Komputer kuantum tetapi tampaknya sulit untuk yang biasa.
Para ahli teori kompleksitas ingin memahami apakah perbedaan nyata dalam kesulitan ini adalah fundamental. Apakah ada sesuatu yang secara intrinsik sulit tentang masalah tertentu, atau apakah kita tidak cukup pintar untuk menghasilkan solusi yang baik? Peneliti menjawab pertanyaan seperti itu dengan menyortir masalah menjadi “kelas kompleksitas”—Semua masalah mudah terjadi dalam satu kelas, misalnya, dan semua masalah yang mudah diperiksa terjadi pada yang lain-dan membuktikan teorema tentang hubungan antara kelas-kelas tersebut.
Sayangnya, memetakan lanskap kesulitan komputasi ternyata, baik, sulit. Jadi pada pertengahan 1970-an, beberapa peneliti mulai mempelajari apa yang akan terjadi jika aturan perhitungan berbeda. Di situlah nubuat masuk.
Seperti Magic 8 Balls, Oracles adalah perangkat yang segera menjawab pertanyaan ya-atau-tidak tanpa mengungkapkan apa pun tentang pekerjaan batin mereka. Tidak seperti Magic 8 Balls, mereka selalu mengatakan ya atau tidak, dan mereka selalu benar – keuntungan menjadi fiksi. Selain itu, oracle yang diberikan hanya akan menjawab jenis pertanyaan tertentu, seperti “apakah angka ini prime?”
Apa yang membuat perangkat fiksi ini bermanfaat untuk memahami dunia nyata? Singkatnya, mereka dapat mengungkapkan koneksi tersembunyi antara kelas kompleksitas yang berbeda.
Ambil dua kelas kompleksitas paling terkenal. Ada kelas masalah yang mudah dipecahkan, yang oleh para peneliti disebut “p,” dan kelas masalah yang mudah diperiksa, yang oleh para peneliti disebut “NP.” Apakah semua masalah yang mudah diperiksa juga mudah dipecahkan? Jika demikian, itu berarti NP akan sama dengan P, dan semua enkripsi akan Mudah retak (di antara konsekuensi lainnya). Para ahli teori kompleksitas mencurigai bahwa NP tidak sama dengan P, tetapi mereka tidak dapat membuktikannya, meskipun mereka telah mencoba untuk menjabarkan hubungan antara kedua kelas untuk lebih dari 50 tahun.
Oracles telah membantu mereka lebih memahami apa yang mereka kerjakan. Para peneliti telah menemukan nubuat yang menjawab pertanyaan yang membantu memecahkan banyak masalah berbeda. Di dunia di mana setiap komputer memiliki hotline ke salah satu nubuat ini, semua masalah yang mudah diperiksa juga akan mudah dipecahkan, dan P akan sama dengan NP. Tapi oracle lain yang kurang membantu memiliki efek sebaliknya. Di dunia yang dihuni oleh nubuat ini, P dan NP akan terbukti berbeda.
Para peneliti telah menggunakan pengetahuan ini untuk mendapatkan pemahaman yang lebih baik tentang masalah P versus NP. Upaya pertama untuk menentukan hubungan antara P dan NP menggunakan trik elegan yang disebut Diagonalisasi Itu sangat penting untuk hasil utama lainnya dalam ilmu komputer. Tetapi peneliti segera diwujudkan Bahwa bukti apa pun yang didasarkan pada diagonalisasi juga berlaku untuk dunia mana pun di mana setiap komputer dapat berkonsultasi dengan oracle yang sama. Doom yang dieja ini, saat oracles mengubah jawaban ke pertanyaan P versus NP. Jika para peneliti dapat menggunakan diagonalisasi untuk membuktikan bahwa P dan NP berbeda di dunia nyata, bukti yang sama akan menyiratkan bahwa P dan NP berbeda di dunia yang diinfus oracle di mana mereka jelas setara. Itu berarti setiap solusi berbasis diagonalisasi untuk masalah P versus NP akan bertentangan dengan diri sendiri. Para peneliti menyimpulkan bahwa mereka akan membutuhkan teknik baru untuk membuat kemajuan.
Oracles juga telah membantu dalam studi komputasi kuantum. Pada 1980 -an dan 1990 -an, para peneliti menemukan cara untuk memanfaatkan fisika kuantum untuk menyelesaikan masalah tertentu dengan cepat yang tampaknya sulit bagi komputer “klasik” biasa. Tetapi apakah masalah ini tampak sulit, atau apakah mereka benar -benar sulit? Membuktikannya dengan satu atau lain cara akan membutuhkan teknik matematika baru yang radikal.
Karena itu, para peneliti telah mempelajari bagaimana komputer kuantum tarif pada masalah yang melibatkan nubuat. Upaya -upaya ini dapat memberikan Bukti tidak langsung Komputer kuantum itu benar -benar lebih kuat daripada yang klasik, dan mereka dapat membantu para peneliti mengeksplorasi tugas baru secara kualitatif di mana komputer kuantum mungkin unggul. Terkadang, mereka bahkan dapat memiliki aplikasi praktis. Pada tahun 1994, ahli matematika terapan Peter Shor terinspirasi oleh a Hasil Oracle Terbaru untuk mengembangkan algoritma kuantum cepat memperhitungkan sejumlah besar—Sebuah tugas yang kesulitannya mendasari sistem kriptografi yang menjaga data online kami tetap aman. Penemuan Shor memulai perlombaan untuk membangun komputer kuantum yang kuat yang berlanjut hingga hari ini.
Sulit untuk memprediksi masa depan teori kompleksitas, tetapi tidak setiap pertanyaan tentang lintasan lapangan sama sulitnya untuk dijawab. Akankah para peneliti terus berkonsultasi dengan nubuat? Tanda menunjuk ke ya.
Cerita asli dicetak ulang dengan izin dari Berapa banyak majalah, publikasi editorial independen dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman publik tentang sains dengan meliput perkembangan penelitian dan tren matematika dan ilmu fisik dan kehidupan.
