Bayangkan Anda sedang dalam upaya untuk memahami hakikat komputasi. Anda berada jauh di tengah hutan belantara, jauh dari jalan apa pun, dan gaib pesan diukir pada batang pohon di sekitar Anda — BPP, AC⁰[m], Σ₂P, YACC, dan ratusan lainnya. Mesin terbang tersebut mencoba memberi tahu Anda sesuatu, tetapi harus mulai dari mana? Anda bahkan tidak bisa menjaga semuanya tetap lurus.

Hanya sedikit peneliti yang telah melakukan hal serupa Russel Impagliazzo untuk mengatasi kekacauan yang tampak ini. Selama 40 tahun, Impagliazzo telah bekerja di garis depan teori kompleksitas komputasi, studi tentang kesulitan intrinsik dari berbagai masalah. Pertanyaan terbuka paling terkenal di bidang ini, yang disebut masalah P versus NP, menanyakan apakah banyak masalah komputasi yang tampaknya sulit ternyata mudah — dengan algoritma yang tepat. Jawabannya akan mempunyai implikasi luas bagi ilmu pengetahuan dan keamanan kriptografi modern.

Pada tahun 1980an dan 1990an, Impagliazzo memainkan peran utama dalam menyatukan landasan teori kriptografi. Pada tahun 1995, ia mengartikulasikan pentingnya perkembangan baru ini dalam sebuah makalah ikonik yang merumuskan kembali solusi yang mungkin untuk P versus NP dan beberapa masalah terkait dalam bahasa yang digunakan. lima dunia hipotetis yang mungkin kita tinggali, yang secara aneh dijuluki Algorithmica, Heuristica, Pessiland, Minicrypt, dan Cryptomania. Lima dunia Impagliazzo telah menginspirasi generasi peneliti, dan mereka terus memandu penelitian di subbidang ilmu pengetahuan yang berkembang pesat. kompleksitas meta.

Dan ini bukan satu-satunya dunia yang dia impikan. Impagliazzo telah lama menjadi penggemar permainan peran meja seperti Dungeons and Dragons, dan dia senang menciptakan seperangkat aturan baru dan pengaturan baru untuk dijelajahi. Semangat ceria yang sama menjiwai praktik komedi improvisasinya selama 30 tahun.

Impagliazzo juga melakukan pekerjaan dasar yang menjelaskan peran mendasar keacakan dalam komputasi. Pada akhir tahun 1970-an, ilmuwan komputer menemukan bahwa keacakan terkadang bisa terjadi meningkatkan algoritma untuk memecahkan masalah yang pada dasarnya bersifat deterministik — sebuah temuan yang berlawanan dengan intuisi yang membingungkan para peneliti selama bertahun-tahun. Karya Impagliazzo dengan ahli teori kompleksitas Avi Wigderson dan peneliti lain pada tahun 1990an menunjukkan bahwa jika masalah komputasi tertentu benar-benar sulit, maka itu adalah masalah yang sulit. selalu mungkin untuk mengubah algoritma yang menggunakan keacakan menjadi algoritma deterministik. Dan sebaliknya, membuktikan bahwa keacakan dapat dihilangkan dari algoritma apapun juga akan membuktikan bahwa masalah yang benar-benar sulit memang ada.

Quanta berbicara dengan Impagliazzo tentang perbedaan antara soal sulit dan teka-teki sulit, berkonsultasi dengan ramalan, dan pelajaran matematika dari komedi improvisasi. Wawancara telah diringkas dan diedit untuk kejelasan.

Kapan pertama kali Anda tertarik pada matematika?

Saya tertarik pada matematika bahkan sebelum saya benar-benar tahu apa itu matematika. Di kelas tiga, nilai matematika saya mulai menurun karena kami harus menghafal tabel perkalian, dan saya menolak. Ibu saya berkata, “Tetapi Russell, kamu menyukai matematika, mengapa kamu tidak melakukan ini?” Dan saya berkata, “Itu bukan matematika, itu menghafal. Matematika sebenarnya tidak melibatkan hafalan.” Yang saya pelajari saat itu hanyalah aritmatika, jadi saya tidak yakin dari mana saya mendapat anggapan bahwa matematika adalah tentang konsep-konsep abstrak.

Bagaimana dengan ilmu komputer? Bagian-bagian dari bidang ini sangat abstrak, tetapi bukan itu yang pertama kali ditemui kebanyakan orang.

Di sekolah menengah, saya pernah mengikuti kursus pemrograman BASIC, tetapi sangat sulit untuk menyelesaikan apa pun. Program-program tersebut harus ditransfer ke kaset kertas, yang harus dijalankan melalui komputer yang sangat tua ini yang sering kali tidak berfungsi dan kertas Anda robek menjadi dua. Jadi menurut saya ilmu komputer itu sangat membosankan.

Saya bermaksud belajar logika. Namun banyak konsep, ketika Anda mencoba memformalkannya, melibatkan komputasi dan terutama batasan komputasi. Pertanyaan seperti “Bagaimana kita mengetahui bahwa segala sesuatu dalam matematika itu benar?” dan “Bagaimana kita memahami kesulitan mengerjakan matematika?” mengarah pada ilmu komputer teoretis, dan teori kompleksitas khususnya.

Beberapa karya Anda yang paling terkenal mengeksplorasi hubungan antara kriptografi dan teori kompleksitas komputasi. Mengapa kedua bidang tersebut saling berhubungan?

Saat Anda menyiapkan sistem kriptografi, Anda perlu membedakan antara pengguna yang sah — orang yang ingin Anda beri akses — dan orang lain. Masalah komputasi yang sulit memberi kita cara untuk membedakan kelompok-kelompok ini berdasarkan apa yang mereka ketahui. Namun jika Anda ingin mengetahui jawaban suatu masalah menjadi cara membedakan dua kelompok orang, Anda tidak bisa hanya menggunakan masalah sulit apa pun — Anda memerlukan teka-teki yang sulit.

Apa perbedaan antara masalah dan teka-teki?

Secara umum, orang yang mengajukan masalah mungkin tidak mengetahui jawabannya. Teka-teki adalah masalah yang dirancang dengan mempertimbangkan jawaban. Jadi mengapa kita membutuhkan teka-teki? Karena kita harus bisa menentukan apakah orang yang seharusnya menyelesaikan masalah itu benar-benar melakukannya. Dalam kehidupan sehari-hari, kita menggunakan teka-teki untuk hiburan, namun kita juga menggunakannya di ruang kelas untuk menguji apakah orang-orang memahami materi tersebut. Inilah yang terjadi dalam kriptografi: Kami menggunakan teka-teki untuk menguji pengetahuan seseorang.

Perbedaan antara kelima dunia tersebut adalah bagaimana mereka menjawab pertanyaan “Apakah ada masalah yang sulit?” dan “Apakah ada teka-teki yang sulit?”

Bagaimana jawaban-jawaban yang berbeda tersebut terjadi?

Di dunia pertama, Algorithmica, tidak ada masalah yang sulit. Anda tidak harus tahu bagaimana seseorang merancang masalah Anda: Anda selalu bisa menyelesaikannya. Heuristica berkata, "Yah, mungkin beberapa soal itu sulit." Lalu kita tiba di Pessiland, di mana banyak soal yang sulit, namun sebagian besar teka-teki tidak. Hampir semua masalah yang saya buat jika saya tahu solusinya, Anda juga akan bisa menyelesaikannya. Semua dunia ini buruk untuk kriptografi.

Di Minicrypt, saya bisa membuat teka-teki yang saya tahu cara memecahkannya yang masih sangat menantang bagi Anda. Dan terakhir, Cryptomania adalah sebuah dunia di mana dua orang dapat berdiri di tempat umum di mana seorang penyadap dapat mendengar dan bersama-sama menciptakan sebuah teka-teki yang masih sulit bagi penyadap.

Apa yang memotivasi Anda untuk menulis makalah lima dunia?

Pada saat itu, diketahui bahwa jawaban yang berbeda terhadap pertanyaan P versus NP akan berdampak besar pada jenis masalah apa yang bisa kita selesaikan dan juga jenis keamanan apa yang bisa kita harapkan, namun perbedaan kualitatif antara berbagai bentuk kemudahan dan kemudahan dapat dicapai. kekerasannya tidak begitu jelas.

Ada makalah yang sangat mendalam beberapa tahun sebelumnya yang memaparkan perbedaan menggunakan banyak pertanyaan yang saling terkait dengan 20 kemungkinan jawaban. Salah satu alasan mengapa saya ingin menulis makalah lima dunia adalah kami telah mencapai banyak kemajuan dalam beberapa tahun tersebut. Sulit menemukan nama untuk 20 kemungkinan dunia.

Jadi mengapa membingkainya seperti itu, sebagai dunia berbeda dengan nama yang unik?

Saya telah setuju untuk menulis makalah ini untuk konferensi. Saya begadang hingga larut malam mencoba mencari tahu apa yang akan saya katakan, dan sekitar jam 1 pagi, pembingkaian dunia yang berbeda sepertinya merupakan ide yang bagus. Dan kemudian saya membacanya keesokan paginya dan sepertinya ide tersebut masih bagus - ini adalah cara untuk menunjukkan bagaimana ide-ide ini benar-benar akan mempengaruhi dunia tanpa terjebak dalam detail kuantitatif. Apa yang membuat saya paling bahagia dengan makalah ini adalah saya mendengar dari orang-orang yang melakukan penelitian dalam kompleksitas bahwa makalah inilah yang membuat mereka tertarik pada bidang tersebut saat masih mahasiswa.

Apakah para peneliti telah mengesampingkan salah satu dari lima kemungkinan dunia?

Kami sebenarnya menambahkan lebih banyak lagi — orang-orang sudah mulai membicarakannya Kebingungan sebagai dunia dengan alat kriptografi yang lebih kuat. Agak menyedihkan bahwa kita mencapai begitu banyak kemajuan pada akhir tahun 1980an dan belum menghilangkan satu pun dunia sejak saat itu. Namun di sisi lain, kita mengetahui lebih banyak tentang hubungan antar dunia dan memiliki gambaran yang jauh lebih jelas tentang seperti apa rupa setiap dunia.

Dunia hipotetis juga memainkan peran lain dalam teori kompleksitas, dalam pembuktian yang mengasumsikan keberadaan “ramalan”. Jadi, pertama-tama, apa sebenarnya ramalan itu?

Bayangkan seseorang membuat perangkat cerdik yang dapat memecahkan suatu masalah tanpa kita mengetahui algoritma untuk memecahkan masalah tersebut. Itulah yang dimaksud dengan ramalan. Jika kita mempunyai perangkat ajaib seperti itu dan kita memasukkannya ke dalam komputer kita, maka perangkat tersebut akan menggeser batasan antara apa yang dapat dihitung dan apa yang tidak dapat dihitung.

Apakah para peneliti mengira kotak ajaib ini benar-benar ada?

Tidak, mereka mungkin tidak ada. Pada awalnya, hasil ramalan agak kontroversial karena bersifat hipotetis. Namun salah satu cara mereka bisa sangat mencerahkan adalah ketika ramalan digunakan untuk memodelkan situasi yang ideal. Katakanlah Anda mencoba untuk menunjukkan bahwa A belum tentu berarti B. Anda mulai dengan pengaturan di mana Anda memiliki A yang paling ekstrim dan menunjukkan bahwa itu masih belum cukup untuk menjamin B. Jika Anda dapat menunjukkan bahwa meskipun semua kemungkinannya adalah menguntungkan Anda, Anda masih belum bisa membuktikan sesuatu, itu bukti yang sangat kuat bahwa itu akan sulit dibuktikan.

Anda juga menemukan hubungan antara kekerasan komputasi dan keacakan. Bagaimana cara kerja koneksi itu?

Ini benar-benar cara untuk mengatakan bahwa jika Anda tidak memahami sesuatu, hal itu mungkin tampak acak. Misalkan saya sedang memikirkan angka antara satu dan seribu. Jika saya memilih nomor tersebut secara acak, Anda mempunyai peluang satu dalam seribu untuk menebaknya. Dan jika saya bertanya - mengikuti Monty Python - “Dalam mil per jam, berapa kecepatan rata-rata burung layang-layang Eropa?” kamu mempunyai peluang yang sama. Mungkin kecepatannya lebih dari satu mil per jam, dan mungkin tidak lebih dari seribu mil per jam.

Ini sebenarnya bukan pertanyaan acak - ini adalah pertanyaan yang bisa dijawab secara deterministik. Kita bisa saja mengukur semua burung layang-layang yang beterbangan, namun sulit untuk menentukannya dengan sumber daya yang terbatas, misalnya tidak memiliki anggaran untuk mengukur kecepatan burung layang-layang dan tidak memiliki persediaan burung layang-layang yang tidak terbatas.

Jadi pemahamannya adalah bahwa permasalahan sulit yang solusinya tidak kita ketahui dapat memberikan sumber bilangan “acak semu” yang terlihat acak.

Berbicara tentang Monty Python, saya tahu Anda sudah lama melakukan komedi improvisasi — bagaimana Anda memulainya?

Saya mulai menjadi asisten profesor di San Diego pada tahun 1991. Dan sekitar tahun '94, saya berpikir, “Saya sebenarnya tidak punya banyak kehidupan di luar departemen.” Jadi saya mendapat koran mingguan gratis, dan saya melihat daftar klub dan kegiatannya. Saya menghilangkan semuanya kecuali komedi improvisasi — saya pikir setidaknya masuk akal bahwa saya akan baik-baik saja dalam hal itu. Saya bertemu istri saya di kelas pemula itu.

Apa yang dia pikirkan?

Dia bilang aku sangat buruk. Ketika Anda seorang ahli logika, Anda dilatih untuk selalu memikirkan nuansa setiap kata. Anda tidak ingin mengatakan sesuatu yang salah. Improvisasi itu bagus karena membalikkan hal itu: Intinya bukanlah mengatakan sesuatu yang sempurna tetapi mengarang sesuatu dengan cepat. Itu kebalikan dari sisa hidupku.

Istri saya yang sekarang istirahat dari kelas, dan ketika dia kembali setahun kemudian, saya berhasil membuatnya terkesan. Itu terjadi 30 tahun yang lalu. Saya masih mengambil kelas yang sama dengan instruktur yang sama.

Apakah melakukan improvisasi telah mengubah cara Anda melakukan pendekatan terhadap penelitian?

Ini adalah praktik yang baik untuk tidak terlalu kritis terhadap setiap pemikiran yang Anda miliki. Itu sangat membantu dalam kolaborasi. Ketika melakukan pekerjaan dengan orang lain, saya sering mengatakan hal-hal seperti, “Tetapi ide itu tidak akan berhasil karena alasan berikut. Itu tidak sepenuhnya benar.” Sebagai improvisasi, Anda harus selalu menerima apa yang dikatakan pasangan Anda. Dan menurut saya itu adalah sikap yang baik untuk dimiliki, terutama ketika Anda melakukan penelitian dengan siswa: Jangan mengabaikan apa yang mereka katakan hanya karena Anda tahu itu tidak benar. Ada banyak ide bagus yang tidak 100% benar.

Seperti apa?

Saat Anda mencoba mendapatkan intuisi untuk suatu masalah, satu hal yang membantu adalah memulai dengan beberapa asumsi yang disederhanakan. Asumsi tersebut biasanya tidak benar, namun dapat membantu Anda membuat peta jalan. Katakan, “Jika saya punya gajah, saya bisa melewati gunung. Tentu saja saya tidak punya gajah. Namun jika saya melakukannya, beginilah cara saya melakukannya.” Dan kemudian Anda menyadari, “Mungkin saya tidak membutuhkan gajah untuk langkah ini. Seekor keledai akan baik-baik saja.”

Bagaimana dengan kecintaan Anda pada permainan peran - apakah hal itu memengaruhi pekerjaan Anda?

Ini mungkin tidak mempengaruhi seluruh penelitian saya, tapi jelas mempengaruhi makalah lima dunia saya. Saya selalu mempunyai ketertarikan umum pada fantasi dan fiksi ilmiah dan memikirkan kemungkinan-kemungkinan dunia yang berbeda - bagaimana jadinya jika semuanya berbeda?

Mengapa permainan peran merupakan cara yang menarik untuk menjelajahi dunia hipotetis?

Orang-orang yang menyukai fiksi spekulatif selalu menciptakan dunia. Tolkien paling terkenal karena hal itu, dan dia memiliki imajinasi yang sangat besar sehingga dunianya benar-benar terasa hidup di dalamnya. Bagi kita yang tidak terlalu imajinatif, cara terbaik untuk mencapainya adalah dengan mengundang orang ke dalam lingkungan Anda, dan sebuah permainan. adalah cara untuk melakukan hal itu. Sekarang ini bukan hanya duniaku. Ini mungkin dimulai seperti yang saya bayangkan, tetapi sama seperti kolaborasi apa pun, karena kontribusi orang lain, kolaborasi ini berkembang jauh melampaui itu.