Уявіть, що ви намагаєтеся зрозуміти саму природу обчислень. Ти глибоко в пустелі, далеко від будь-яких стежок, і незрозумілий повідомлення вирізані на стовбурах дерев навколо вас — BPP, AC⁰[м], Σ₂P, YACC та сотні інших. Гліфи намагаються вам щось сказати, але з чого почати? Ви навіть не можете тримати їх усіх прямо.

Небагато дослідників зробили стільки, скільки Рассел Імпальяццо щоб подолати цей удаваний хаос. Протягом 40 років Імпальяццо працював на передньому краї теорії обчислювальної складності, вивчення внутрішньої складності різних проблем. Найвідоміше відкрите питання в цій галузі, яке називається проблемою P проти NP, запитує, чи багато, здавалося б, складних обчислювальних задач є насправді легкими — з правильним алгоритмом. Відповідь мала б далекосяжні наслідки для науки та безпеки сучасної криптографії.

У 1980-х і 1990-х роках Impagliazzo відіграв провідну роль в об'єднанні теоретичні основи криптографії. У 1995 році він сформулював важливість цих нових розробок у знаковій статті, яка переформулювала можливі рішення для P проти NP та кілька пов’язаних проблем мовою п'ять гіпотетичних світів ми могли б жити, химерно названі Algorithmica, Heuristica, Pessiland, Minicrypt і Cryptomania. П’ять світів Імпальяццо надихнули ціле покоління дослідників, і вони продовжують спрямовувати дослідження в процвітаючій підсфері метакомплексність.

І це не єдині світи, про які він мріяв. Імпальяццо все життя був прихильником настільних рольових ігор, як-от Dungeons and Dragons, і він із задоволенням винаходить нові набори правил і нові налаштування для вивчення. Той же грайливий дух оживляє його 30-річну практику імпровізаційної комедії.

Імпальяццо також виконав основоположну роботу, з’ясувавши фундаментальну роль випадковості в обчисленнях. Наприкінці 1970-х комп’ютерні вчені виявили, що випадковість іноді може бути вдосконалити алгоритми для розв’язання детермінованих за своєю суттю проблем — суперечливий висновок, який роками бентежив дослідників. Робота Імпальяццо з теоретиком складності Аві Вігдерсон та інші дослідники в 1990-х роках показали, що якщо певні обчислювальні проблеми дійсно фундаментально складні, то це завжди можливо для перетворення алгоритмів, які використовують випадковість, у детерміновані. І навпаки, доводячи, що випадковість можна усунути з будь-якого алгоритму також довів би що справді важкі проблеми існують.

Quanta поговорив з Імпальяццо про різницю між важкими проблемами та складними головоломками, консультаціями з оракулами та математичними уроками комедії-імпровізації. Інтерв’ю було скорочено та відредаговано для ясності.

Коли ви вперше зацікавилися математикою?

Мене цікавила математика ще до того, як я справді знав, що це таке. У третьому класі мої оцінки з математики почали падати, тому що ми мали вчити таблицю множення, а я відмовився. Моя мама сказала: «Але Рассел, ти любиш математику, чому ти цим не займаєшся?» І я сказав: «Це не математика, це запам’ятовування. Справжня математика не передбачає запам’ятовування». Усе, чого я на той момент навчився, це арифметика, тому я не знаю, звідки я взяв уявлення, що математика стосується абстрактних понять.

А як щодо інформатики? Частини поля дуже абстрактні, але вони не є тим, з чим більшість людей стикається вперше.

У середній школі я проходив курс програмування BASIC, але мені було дуже важко щось зробити. Програми потрібно було перенести на паперові стрічки, які потрібно було пропустити через цей дуже старий комп’ютер, який часто виходив з ладу та розривав папір навпіл. Тож я вважав, що інформатика страшенно нудна.

Я мав намір вивчати логіку. Але багато концепцій, коли ви намагаєтеся їх фактично формалізувати, передбачають обчислення та особливо обмеження на обчислення. Питання на зразок «Як ми дізнаємося, що те, що в математиці правдиве?» і «Як ми розуміємо складність вивчення математики?» привів до теоретичної інформатики, і особливо до теорії складності.

Деякі з ваших найвідоміших робіт досліджують зв’язки між криптографією та теорією обчислювальної складності. Чому ці два поля пов’язані?

Коли ви налаштовуєте криптографічну систему, вам потрібно розрізняти законних користувачів — людей, яким ви хочете надати доступ — і всіх інших. Складні обчислювальні завдання дають нам спосіб розрізняти ці групи на основі того, що вони знають. Але якщо ви хочете, щоб відповідь на проблему була способом розрізнити дві групи людей, ви не можете використовувати будь-яку складну задачу — вам потрібна складна головоломка.

Яка різниця між проблемою та головоломкою?

Загалом, людина, яка ставить проблему, може не знати відповіді. Головоломка — це завдання, розроблене з урахуванням відповіді. Так навіщо нам головоломка? Тому що ми повинні мати можливість визначити, чи людина, яка нібито це розгадала, справді це зробила. У повсякденному житті ми використовуємо головоломки для розваги, але ми також використовуємо їх у класі, щоб перевірити, чи люди зрозуміли матеріал. Ось що відбувається в криптографії: ми використовуємо головоломки, щоб перевірити чиїсь знання.

Різниця між п’ятьма світами полягає в тому, як вони відповідають на запитання «Чи є складні проблеми?» і «Чи бувають складні головоломки?»

Як виглядають ці різні відповіді?

У першому світі, Algorithmica, жодні проблеми не є складними. Вам не потрібно знати, як хтось створив вашу проблему: ви завжди можете її вирішити. Heuristica каже: «Ну, можливо, кілька проблем є складними». Потім ми потрапляємо в Пессіленд, де багато проблем складні, але більшість головоломок — ні. Майже будь-яку задачу, яку я вигадую, і я знаю її рішення, ти також зможеш її вирішити. Усі ці світи шкідливі для криптографії.

У Minicrypt я можу створювати головоломки, які я знаю, як розв’язувати, але які все ще є справді складними для вас. І, нарешті, Cryptomania — це світ, у якому двоє людей можуть стояти в громадському місці, де підслуховувач може почути, і разом створити головоломку, яка все ще є важкою для підслухувача.

Що спонукало вас написати статтю про п’ять світів?

У той час було відомо, що різні відповіді на питання P проти NP матимуть великий вплив на те, які проблеми ми можемо вирішити, а також на який тип безпеки ми можемо сподіватися, але якісні відмінності між різними формами легкості та твердість не була дуже ясною.

Лише кілька років тому була дуже прониклива стаття, яка викладала відмінності за допомогою багатьох взаємопов’язаних запитань із приблизно 20 можливими відповідями. Однією з причин, чому я хотів написати статтю про п’ять світів, було те, що ми досягли величезного прогресу за ці кілька років. Важко було б знайти назви для 20 можливих світів.

Тож навіщо оформляти це таким чином, як різні світи з химерними назвами?

Я погодився написати цю статтю для конференції. Я не спав допізна, намагаючись зрозуміти, що я збираюся сказати, і десь близько першої ночі обрамлення різних світів здалося гарною ідеєю. А потім я прочитав це наступного ранку, і це все ще здавалося нормальною ідеєю — це був спосіб показати, як ці ідеї насправді вплинуть на світ, не зациклюючись на кількісних деталях. Що мене найбільше тішить у цій роботі, так це те, що я чув від людей, які займаються дослідженнями комплексності, що це була стаття, яка зацікавила їх цією сферою, коли вони були студентами.

Чи дослідники виключили будь-який із п’яти можливих світів?

Ми фактично додаємо більше — люди почали говорити про це Обфустопія як світ ще потужніших криптографічних інструментів. Трохи пригнічує те, що ми досягли такого прогресу наприкінці 1980-х років і з тих пір не знищили жодного світу. Але з іншого боку, ми знаємо набагато більше про зв’язки між світами та маємо набагато чіткіше зображення того, як би виглядав кожен світ.

Гіпотетичні світи також відіграють іншу роль у теорії складності, у доказах, які припускають існування «оракулів». Отже, по-перше, що таке оракул?

Уявіть собі, що хтось створює геніальний пристрій, який може вирішити якусь проблему, не знаючи алгоритму вирішення цієї проблеми. Ось що таке оракул. Якби ми мали такий дивовижний пристрій і помістили його в наші комп’ютери, він міг би змінити межу між тим, що можна обчислити, і тим, що не можна обчислити.

Чи думають дослідники, що ці чарівні скриньки насправді можуть існувати?

Ні, напевно їх не існує. На початку результати Oracle були дещо суперечливими, оскільки вони були гіпотетичними. Але один із способів, коли вони можуть бути дуже повчальними, це коли оракул використовується для моделювання ідеальної ситуації. Скажімо, ви намагаєтеся показати, що А не обов’язково означає Б. Ви починаєте з налаштування, де у вас найбільше А, і показуєте, що цього все ще недостатньо, щоб гарантувати Б. Якщо ви можете показати, що навіть якщо всі шанси на вашу користь ви все одно не можете щось довести, це дійсно вагомі докази, які буде важко довести.

Ви також виявили зв’язок між складністю обчислень і випадковістю. Як працює цей зв'язок?

Це дійсно спосіб сказати, що якщо ви чогось не розумієте, це може здатися випадковим. Припустімо, що я думаю про число від одного до тисячі. Якщо я виберу число навмання, ви матимете шанс один із тисячі вгадати його. І якщо я запитаю — слідом за Монті Пайтоном — «яка середня швидкість польоту європейської ластівки в милях на годину?» у вас приблизно такий же шанс. Ймовірно, він рухається більше однієї милі на годину, і, мабуть, не більше тисячі миль на годину.

Насправді це не випадкове — це питання, на яке можна відповісти детерміновано. Ми могли б просто виміряти всіх ластівок, які літають навколо, але це начебто важко визначити з обмеженими ресурсами, як-от відсутність бюджету на вимірювання швидкості ковтання та відсутність нескінченної кількості ластівок.

Отже, розуміння полягає в тому, що складні проблеми, розв’язки яких ми не знаємо, можуть бути джерелом «псевдовипадкових» чисел, які виглядають випадковими.

Говорячи про Monty Python, я знаю, що ти вже давно займаєшся комедією-імпровізацією — як ти почав?

Я почав працювати асистентом професора в Сан-Дієго в 1991 році. І приблизно в 94 році я подумав: «Мені справді не так багато життя поза кафедрою». Тож я отримав безкоштовну щотижневу газету й переглянув список клубів і заходів. Я виключив усе, окрім комедії-імпровізації — я вважав, що це принаймні правдоподібно, що я впораюся з цим. Я познайомився зі своєю дружиною в тому класі для початківців.

Що вона подумала?

Вона каже, що я був справді жахливим. Коли ви логік, ви навчені завжди думати про нюанси кожного слова. Ви ж не хочете сказати щось невірне. Improv чудовий тим, що він перевертає це: справа не в тому, щоб сказати щось ідеальне, а в тому, щоб щось швидко придумати. Це була протилежність решті мого життя.

Моя нинішня дружина взяла перерву в класі, і коли вона повернулася через рік, мені вдалося справити на неї враження. Це було 30 років тому. Я все ще ходжу на те саме заняття з тим же інструктором.

Чи змінила вдосконалення ваш підхід до дослідження?

Це хороша практика, щоб не бути гіперкритичним щодо кожної своєї думки. Це особливо корисно у співпраці. Працюючи з іншими людьми, я говорив щось на кшталт: «Але ця ідея не спрацює з наступної причини. Це не зовсім правда». В імпровізації ви завжди повинні приймати те, що говорить ваш партнер. І я вважаю, що це гарне ставлення, особливо коли ви проводите дослідження зі студентами: не відкидайте те, що вони говорять, лише тому, що ви знаєте, що це неправильно. Є багато хороших ідей, які не є на 100% правильними.

Як що?

Коли ви намагаєтесь отримати інтуїцію для вирішення проблеми, одне, що допомагає, це почати з деяких спрощених припущень. Зазвичай ці припущення не відповідають дійсності, але вони можуть допомогти вам скласти дорожню карту. Скажіть: «Якби у мене був слон, я міг би перебратися через гори. Звичайно, у мене немає слона. Але якби я це зробив, ось як би я це зробив». І тоді ти розумієш: «Ну, можливо, мені не потрібен слон для цього кроку. Мул підійде».

А як щодо вашої любові до рольових ігор — це взагалі вплинуло на вашу роботу?

Можливо, це не вплинуло на всі мої дослідження, але точно вплинуло на мою статтю про п’ять світів. Мене завжди цікавили фентезі та наукова фантастика, а також придумування різних можливих світів — що було б, якби все було інакше?

Чому рольові ігри є таким захоплюючим способом дослідження гіпотетичних світів?

Люди, які захоплюються спекулятивною фантастикою, завжди винаходили світи. Толкін найбільше відомий завдяки цьому, і він мав таку величезну уяву, що його світ справді здавався живим. Для тих із нас, хто не має такої уяви, найкращий спосіб досягти цього — запросити людей у ​​своє середовище та гру це спосіб зробити це. Тепер це не просто мій світ. Можливо, все почалося так, як я собі це уявляв, але, як і в будь-якій співпраці, завдяки внеску всіх інших, це розвинулося набагато далі.