Mengapa Ilmuwan Komputer membutuhkan oracles seperti bola ajaib 8

Versi aslinya dari cerita ini muncul di majalah Quanta.

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 untuk 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? Para peneliti menjawab pertanyaan-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 bahwa NP akan sama dengan P, dan semua enkripsi akan mudah dipecahkan (di antara konsekuensi lainnya). Para ahli teori kompleksitas menduga bahwa NP tidak sama dengan P, tetapi mereka tidak dapat membuktikannya, meskipun mereka telah mencoba untuk menjabarkan hubungan antara kedua kelas selama 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.