50-річний шлях теорії складності до межі знань | Журнал Quanta

У перший тиждень осіннього семестру 2007 року Марко Кармозіно потягнувся на курс математики, необхідний для всіх спеціальностей з інформатики в Університеті Массачусетса, Амгерст. Кармозіно, студент другого курсу, розглядав можливість кинути коледж, щоб розробляти відеоігри. Потім професор поставив просте запитання, яке змінило хід його життя: як ви знаєте, що математика справді працює?

«Це змусило мене сісти й звернути увагу», — згадує Кармозіно, тепер спеціаліст-теоретик в IBM. Він записався на факультативний семінар, присвячений роботі Курта Ґоделя, чиї запаморочливі самореференційні аргументи вперше розкрили межі математичних міркувань і створили основу для всієї майбутньої роботи над фундаментальними межами обчислень. Це було багато, щоб прийняти.

«Я на 100% не зрозумів», — сказав Кармозіно. «Але я знав, що хочу».

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

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

"Немає дорожньої карти", - сказав Майкл Сіпсер, досвідчений теоретик комплексності в Массачусетському технологічному інституті, який витратив роки на боротьбу з проблемою в 1980-х роках. «Це ніби ти йдеш у пустелю».

Здається, що довести, що обчислювальні проблеми важко розв’язати, саме по собі є важким завданням. Але чому це так важко? І наскільки це важко? Кармозіно та інші дослідники в галузі метаскладності переформулювали подібні питання як обчислювальні проблеми, просуваючи поле вперед, повертаючи лінзу теорії складності назад на себе.

«Ви можете подумати: «Добре, це якось круто. Можливо, прихильники теорії складності збожеволіли», — сказав він Рахул Іланго, аспірант Массачусетського технологічного інституту, який досяг одні з найцікавіших останніх результатів у цій галузі.

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

«Стало зрозуміло, що мета-складність близька до суті», — сказав він Скотт Аронсон, теоретик складності в Техаському університеті в Остіні.

Це історія про довгий і звивистий шлях, який привів дослідників від проблеми P проти NP до мета-складності. Це була непроста подорож — дорога всіяна помилковими поворотами та блокпостами, і вона повертається назад і знову. Проте для дослідників мета-складності ця подорож у незвіданий ландшафт є окремою винагородою. Почніть задавати, здавалося б, прості питання, сказав Валентин Кабанець, теоретик складності з Університету Саймона Фрейзера в Канаді, і «ви не уявляєте, куди ви збираєтесь піти».

Відомі невідомі

Проблема P проти NP завдячує своїй тьмяній назві звичці прихильників теорії складності сортувати обчислювальні проблеми на широкі групи.класи складності” з мітками, що нагадують символи Nasdaq. Обчислювальна задача - це така, яка в принципі може бути розв'язана за допомогою алгоритму - точно визначеного списку інструкцій. Але не всі алгоритми однаково корисні, і варіація серед алгоритмів натякає на фундаментальні відмінності між проблемами в різних класах. Завдання для теоретиків складності полягає в тому, щоб перетворити ці натяки на строгі теореми про зв’язки між класами складності.

Ці відносини відображають незмінні істини про обчислення, які виходять далеко за межі будь-якої конкретної технології. «Це як відкриття законів Всесвіту», – сказав Кабанець.

«P» і «NP» є двома найвідомішими членами a зростаючий звіринець сотень класів складності. Грубо кажучи, P — це клас задач, які можна легко розв’язати, як список за алфавітом. NP — це клас задач із легко перевіреними рішеннями, як-от головоломки судоку. Оскільки всі задачі, які легко розв’язуються, також легко перевірити, задачі з P є також і з NP. Але деякі проблеми NP здаються складними для розв’язання — ви не можете одразу інтуїтивно зрозуміти розв’язання головоломки судоку, попередньо не випробувавши багато можливостей. Чи може бути так, що ця удавана твердість — лише ілюзія — що існує єдиний простий трюк для вирішення кожної проблеми, яку легко перевірити?

Якщо так, то P = NP: два класи еквівалентні. Якщо це так, мусить існувати якийсь алгоритм, який полегшить розв’язання величезних головоломок судоку, оптимізує глобальні маршрути доставки, зламає найсучасніше шифрування та автоматизує докази математичних теорем. Якщо P ≠ NP, то багато обчислювальних проблем, які в принципі розв’язні, на практиці назавжди залишаться поза нашим розумінням.

Дослідників хвилювали обмеження формальних математичних міркувань задовго до того, як була вперше сформульована проблема P проти NP — справді, задовго до початку сучасної інформатики. У 1921 році, борючись з тим самим питанням, яке приверне увагу Кармозіно майже століття потому, математик Девід Гільберт запропонував дослідницьку програму для обґрунтування математики в абсолютній впевненості. Він сподівався почати з кількох простих припущень, які називаються аксіомами, і вивести єдину математичну теорію, яка відповідатиме трьом ключовим критеріям.

Перша умова Гільберта, послідовність, полягала в суттєвій вимогі, щоб математика була вільною від протиріч: якби два суперечливі твердження можна було б довести, виходячи з однакових аксіом, уся теорія була б непоправною. Але теорія може бути вільною від протиріч і все ж обмеженою в своєму охопленні. Це було мотивацією для другої умови Гільберта, повноти: вимога, щоб усі математичні твердження були або доведено істинними, або доведено хибними. Його третій критерій, розв'язність, вимагав однозначної механічної процедури для визначення того, чи є будь-яке математичне твердження істинним чи хибним. Виступаючи на конференції в 1930 році, Гільберт заявив: «Нашим гаслом буде «Ми повинні знати, ми будемо знати»».

Всього через рік Гедель завдав першого удару мрії Гільберта. Він доведений що заперечне твердження на кшталт «це твердження недоведене» може бути отримано з будь-якого відповідного набору аксіом. Якщо таке твердження справді неможливо довести, то теорія є неповною, але якщо воно доведено, то теорія суперечлива — результат ще гірший. У тій самій статті Гедель також довів, що жодна математична теорія ніколи не зможе довести свою послідовність.

Дослідники все ще мали надію на те, що майбутня теорія математики, хоч і обов’язково неповна, все ж може бути доведена. Можливо, вони могли б розробити процедури, які б ідентифікували всі доказові твердження, уникаючи при цьому неприємних пропозицій, таких як твердження Геделя. Біда полягала в тому, що ніхто не знав, як міркувати про ці гіпотетичні процедури.

Потім у 1936 році 23-річний аспірант на ім’я Алан Тюрінг перефразував умову розв’язності Гільберта незнайомою тоді мовою обчислень і завдав їй смертельного удару. Тьюрінг сформулював математичну модель, тепер відому як Turing machine — який міг би представляти всі можливі алгоритми, і показав, що якби процедура Гільберта існувала, вона б відповідала цій моделі. Потім він використав самореферентні методи, такі як Гедель доводити існування нерозв’язних тверджень — або, що еквівалентно, необчислюваних проблем, які не може вирішити жоден алгоритм.

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

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

«Виникає багата теорія, і ми більше не знаємо відповідей», — сказав Кармозіно.

Розбіжні шляхи

Щоб проілюструвати, наскільки заплутаними можуть бути питання про твердість, давайте розглянемо пару тісно пов’язаних задач із використанням графіків. Це мережі точок, званих вузлами, з’єднаних лініями, званими ребрами. Комп’ютерники використовують їх для моделювання всього квантове обчислення до потік транспорту.

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

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

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

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

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

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

І проблема Гамільтонова шляху, і проблема Ейлера належать до класу складності NP, визначеного для включення всіх проблем, розв’язки яких можна перевірити за допомогою поліноміальних алгоритмів. Проблема шляху Ейлера також належить до класу P, оскільки поліноміальний алгоритм може розв’язати її, але, схоже, це не вірно для проблеми шляху Гамільтона. Чому ці дві задачі з графіками, такі зовні схожі, мають так різко відрізнятися? Це суть проблеми P проти NP.

Універсально жорсткий

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

Потім у 1971 році, протягом року після переїзду в Університет Торонто після того, як йому було відмовлено в посаді в Сполучених Штатах, теоретик складності Стівен Кук опубліковано надзвичайний результат. Він визначив конкретну проблему NP з дивною особливістю: якщо існує поліноміальний алгоритм, який може вирішити цю проблему, він також може вирішити будь-яку іншу проблему в NP. «Універсальна» проблема Кука, здавалося, була самотньою колонкою, що підтримувала клас очевидно складних проблем, відокремлюючи їх від легких проблем, що знаходяться нижче. Зламай цю одну проблему, і решта NP впаде.

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

Приблизно в цей же час аспірант Радянського Союзу ім Леонід Левін довів а аналогічний результат, за винятком того, що він визначив кілька різних універсальних проблем. Крім того, американський теоретик складності Річард Карп доведений що властивість універсальності, визначена Куком (і Левіним, хоча Карп і Кук знали про роботу Левіна лише через роки), сама по собі була майже універсальною. Майже кожна проблема NP без відомого поліноміального алгоритму — тобто майже кожна легко перевірена проблема, яка здавалася важкою — мала ту саму властивість, яка стала відомою як NP-повнота.

Це означає, що всі NP-повні задачі — задача Гамільтонова шляху, судоку та тисячі інших — у точному розумінні еквівалентні. «У вас є всі ці різні природні завдання, і всі вони магічним чином виявляються одним і тим же завданням», — сказав Іланго. «І ми досі не знаємо, чи можливе це завдання чи ні».

Вирішення складності будь-якої NP-повної проблеми було б достатнім для вирішення питання P проти NP. Якщо P ≠ NP, відмінність між легкими та складними задачами утримується тисячами стовпців, які однаково сильні. Якщо P = NP, вся будівля балансує на межі краху, просто чекаючи, поки впаде один шматок.

Кук, Левін і Карп об’єднали, здавалося б, багато не пов’язаних між собою проблем. Тепер теоретикам комплексності залишалося вирішити одну проблему: P = NP чи ні?

Через XNUMX років це питання залишається без відповіді. Кабанець порівнював міркування про межі обчислень із дослідженням величезної території без жодного відчуття загальної картини. Істота з необмеженою обчислювальною потужністю могла б дивитися з вершини гори й охоплювати весь ландшафт одразу, але прості смертні не можуть розраховувати на таку перевагу. «Ті з нас, хто внизу гори, можуть спробувати пострибати вгору та вниз, щоб краще побачити», — сказав він.

Припустимо, що P = NP. Щоб довести це, дослідникам потрібно буде знайти швидкий алгоритм для NP-повної проблеми, яка може ховатися в якомусь незрозумілому куточку цього величезного ландшафту. Немає жодної гарантії, що вони знайдуть його найближчим часом: теоретики складності час від часу бувають відкритий геніальні алгоритми для, здавалося б, складних (хоча і не NP-повних) проблем лише після десятиліть роботи.

Тепер припустимо, що P ≠ NP. Довести це здається ще важчим. Теоретики складності повинні були б встановити, що не може існувати швидкий алгоритм, який би ефективно передбачав і перешкоджав найкращим зусиллям усіх майбутніх дослідників.

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

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

«Я подумав: «Вау, мені потрібно поставитися до цього серйозно», — згадував Кармозіно. Невдовзі він був настільки поглинений предметом, що його наставник м’яко запропонував йому переглянути свої плани після закінчення навчання.

«Він сказав: «Знаєте, якщо ви хочете продовжувати займатися цим, якщо ви хочете продовжувати займатися теоретичною інформатикою та теорією складності, ви можете: це називається аспірантура», — сказав Кармозіно. Отримавши ступінь магістра, він переїхав до Сан-Дієго в 2012 році, щоб працювати над докторською дисертацією під керівництвом Імпальяццо.

Спочатку головною метою Кармозіно було краще зрозуміти а орієнтирний папір з двох десятиліть тому, які захопили його уяву. Ця стаття, за теоретиками складності Олександр Разборов та Стівен Рудіч, показав, що певна «природна» стратегія для доведення P ≠ NP майже напевно зазнає невдачі, оскільки успіх буде досягнутий високою ціною — повним розладом криптографії — що дослідники вважали дуже малоймовірним. Дослідники інтерпретували результат Разборова і Рудіча як перешкоду для цього популярного підходу до доведення P ≠ NP.

Цей «природний бар’єр доказів» є лише одним із багатьох відомих бар’єрів для вирішення відкритих проблем у теорії складності. Кожен діє як блокпост, попереджаючи, що шлях, який здається багатообіцяючим, насправді є глухим кутом. Разом ці бар’єри вказують на те, що будь-який доказ, який розв’язує проблему P проти NP, повинен радикально відрізнятися від будь-якого доказу, який використовувався в минулому; тому більшість дослідників вважають, що рішення ще далеко. Але принаймні бар'єри підказують їм, куди не дивитися.

«Теорія складності водночас проклята й благословенна багатьма бар’єрами», — сказав Іланго.

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

Але щоб пройти шлях від природного бар’єру доказів до метаскладності, нам доведеться повернутися до того місця, де ми залишили дослідників у 1970-х роках, коли вони вперше почали вирішувати проблему P проти NP. Чому було так важко довести проблеми?

Окружний шлях

Спочатку дослідники намагалися довести, що P ≠ NP — тобто довести, що деякі проблеми NP не розв’язуються жодним можливим поліноміальним алгоритмом — використовуючи варіації методів, використаних Тьюрингом, щоб довести, що деякі проблеми не розв’язуються жодним алгоритмом. . Але вони швидко відкритий доказ того, що ці методи не працюватимуть — перша серйозна перешкода для вирішення питання P проти NP. Тож вони почали шукати інший підхід, і незабаром знайшли його в роботі сучасника Тюрінга Клод Шеннон.

Шеннон, який виріс у маленькому містечку на півночі Мічигану, здавався малоймовірною постаттю, яка почала б інформаційну епоху. Проте він продемонстрував міждисциплінарний характер нової дисципліни інформатики, почуваючись однаково добре в електротехніці та математичній логіці. У його магістерська роботаШеннон показав, як схеми, виготовлені з електромеханічних перемикачів, можуть представляти логічні вирази, що містять булеві змінні — величини, які можуть приймати лише два значення (наприклад, істина чи хибність, або 1 і 0).

У цих виразах булеві змінні пов’язані між собою «логічними воротами» І, АБО та НІ. Елементарний вираз A AND B, наприклад, є істинним, коли і A, і B є істинними, і false в іншому випадку; А АБО В, з іншого боку, є істинним, якщо принаймні одна з двох змінних є істинною. Шлюз NOT ще простіший: він інвертує значення однієї змінної. Маючи достатню кількість цих основних будівельних блоків, ви можете виконувати будь-які обчислення.

«Зрештою, коли ви дивитеся на свій комп’ютер, що він робить? Він працює по ланцюгу, — сказав Іланго.

Робота Шеннона запропонувала теоретикам новий спосіб думати про складність обчислювальних проблем, що називається «складністю схем», хоча схеми, про які йде мова, є лише математичними абстракціями. Якийсь час дослідники вважали, що цей підхід може стати способом розв’язання P проти NP, але зрештою слід наткнувся на природний бар’єр доказів.

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

«Я розумію, що люди почали працювати над складністю схем, тому що вони вирішили, що машини Тьюрінга надто складні», — сказав Райан Вільямс, теоретик складності в MIT. «Ми можемо досліджувати ланцюги ворота за воротами».

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

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

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

Це була стратегія, яку дотримувалися більшість теоретиків складності у 1980-х роках. І шанси були на їхньому боці. Шеннон мав доведений у 1949 році майже кожна булева таблиця істинності (яка є лише довгим списком усіх можливих входів і виходів булевої функції фіксованого розміру) має складність схеми, яка є практично максимально можливою. Він використав приголомшливо простий аргумент: існує набагато менше способів об’єднати невелику кількість воріт, ніж способів об’єднати багато воріт.

«Просто не вистачає малих ланцюгів, щоб обійти», — сказав Ааронсон.

Тож прихильники теорії складності опинилися в курйозній ситуації. Якщо майже кожна таблиця істинності має високу складність схеми, то майже кожну булеву функцію важко обчислити. Дослідникам просто потрібно було ідентифікувати одну таку функцію, яка, як відомо, належала до класу NP. Наскільки важко це може бути?

Crypto Bros

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

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

У 1985 році Разборов зробив наступний великий крок. Він щойно почав навчання в аспірантурі в Москві й випадково приєднався до цієї роботи, коли вирішував задачу в іншій галузі математики, де виявилося, що розв’язання проблеми P проти NP є необхідною умовою.

«Мені просто пощастило, що я не знав, наскільки складна ця проблема», — сказав Разборов. «Інакше, можливо, я б навіть не почав».

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

«Було якесь загальнолюдське відчуття, що ще один крок, ще один удар, і ми його отримаємо», — сказав Разборов. Але не так сталося. Сам Разборов довів, що його метод зазнав би невдачі, якби до суміші НЕ були додані гейти, і ніхто не міг знайти іншого шляху вперед. Минали роки, і він почав дивуватися, чому стежка зникла.

У Сполучених Штатах Рудіч розмірковував над тим же питанням. Вони з Імпальяццо були однокурсниками коледжу, які разом навчалися в аспірантурі. Їхня дружба була викликана спільним захопленням самопосиланнями Геделя й Тюрінга на докази та їхній вплив на основи математики й інформатики.

«Наш жарт полягав у тому, що ми збиралися отримати кнопку з написом «автопосилання», — сказав Імпальяццо.

Будучи аспірантами, і Рудіч, і Імпальяццо працювали над теоретико-складними основами криптографії, предметом, який пропонує, мабуть, найкращу практичну мотивацію для спроби довести P ≠ NP. Криптографи приховують секретні повідомлення, маскуючи їх у «псевдовипадковість» — повідомлення, зашифроване таким чином, виглядатиме як випадкова суміш чисел для будь-якого підслуховувача, але все одно його може розшифрувати одержувач. Але як ви можете бути впевнені, що потенційному підслухувачу буде надто важко зламати код?

Ось тут і з’являється теорія складності. Методи шифрування, які найбільш широко використовуються сьогодні, базуються на, здавалося б, складних проблемах NP — щоб розшифрувати повідомлення, зловмиснику знадобиться ще не відкритий швидкий алгоритм для вирішення проблеми. Щоб переконатися, що ці методи справді безпечні, потрібно довести, що P ≠ NP. За словами Сіпсера, без доказу все, що ви можете зробити, це «сподіватися, що той, від кого ви намагаєтесь зберегти таємницю, не є кращим математиком, ніж ви».

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

Напруга в основі природного бар’єру доказів полягає в тому, що завдання відрізнити функції високої складності від функцій низької складності подібне до завдання відрізнити справжню випадковість від псевдовипадковості, яка використовується для шифрування повідомлень. Ми хотіли б показати, що функції високої складності категорично відрізняються від функцій низької складності, щоб довести P ≠ NP. Але ми також хотіли б, щоб псевдовипадковість не відрізнялася від випадковості, щоб бути впевненими в безпеці криптографії. Можливо, ми не можемо мати обидва способи.

Жорстокий жарт

У 1994 році Разборов і Рудіч зрозуміли, що вони дійшли схожих висновків, і почали працювати разом, щоб об’єднати отримані результати. Спочатку вони помітили, що всі попередні спроби довести P ≠ NP за допомогою складності схеми приймали ту саму загальну стратегію: визначити спеціальну властивість NP-повної булевої функції, а потім довести, що жодна легка для обчислення функція не може поділитися цією властивістю. Це показало б, що обрану NP-повну функцію справді важко обчислити, доводячи P ≠ NP.

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

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

«Ви майже не можете не отримати більше, ніж очікували», — сказав Кармозіно.

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

Щоб зрозуміти цей зв’язок, уявіть, що ви дивитеся на вихідний стовпець у таблиці істинності булевої функції з багатьма вхідними змінними та замінюєте кожне «true» на 1 і кожне «false» на 0:

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

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

З іншого боку, якщо безпечна криптографія можлива, то природні докази не є життєздатною стратегією для підтвердження P ≠ NP — необхідної умови для безпечної криптографії. Коротше кажучи, це природний доказовий бар’єр. Здавалося, ніби теоретики складності отримали злий жарт.

«Якщо ви вірите в твердість, то повинні вірити, що твердість важко довести», – сказав Кабанець.

В метавселенну

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

«Існує така інтуїція, що «о, оскільки P ≠ NP, важко довести, що P ≠ NP», — сказав Вільямс. «Але щоб навіть зрозуміти цю інтуїцію, ви повинні почати думати про завдання довести щось на зразок P ≠ NP як обчислювальну задачу».

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

«Я хотів зробити щось більш академічне, — згадував Кабанець. «А ще мені було цікаво побачити світ». Він переїхав до Канади для навчання в аспірантурі, і саме там він дізнався про природний доказовий бар’єр. Як і Кармозіно, Кабанець був вражений результатом. «Цей зв’язок між вами здавався дуже глибоким», — сказав він.

У 2000 році, ближче до кінця навчання в аспірантурі, він виявив, що природний бар’єр доказів постійно виникає в його розмовах з Цзінь-Ї Цай, теоретик складності, який у той час відвідав Торонто у відпустці. Вони почали сприймати бар’єр не як перешкоду, а як запрошення — можливість точно дослідити, наскільки важко доводити проблеми. The папір в якій вони виклали цю нову перспективу, стане однією з найвпливовіших ранніх робіт у зароджуваній галузі мета-складності.

Стаття Кабанця та Кая висвітлила обчислювальну проблему, приховану у формулюванні природного доказового бар’єру Разборова та Рудіча: за таблицею істинності булевої функції визначте, чи має вона високу чи низьку складність схеми. Вони назвали це проблемою мінімального розміру схеми або MCSP.

MCSP — це квінтесенція проблеми мета-складності: обчислювальної проблеми, предметом якої є не теорія графів чи інша зовнішня тема, а сама теорія складності. Дійсно, це схоже на кількісну версію питання, яке спонукало теоретиків складності розглядати P проти NP, використовуючи підхід складності схеми в 1980-х роках: які булеві функції важко обчислити, а які легко?

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

Теоретики складності не хвилюються, що цей магічний алгоритм позбавить їх роботи — вони не думають, що він взагалі існує, тому що Разборов і Рудіч показали, що будь-який такий алгоритм для розрізнення таблиць істинності високої складності від таблиць низької складності зробив би криптографію неможливо. Це означає, що MCSP, ймовірно, є складною обчислювальною проблемою. Але наскільки це важко? Чи є вона NP-повною, як проблема Гамільтонового шляху та майже будь-яка інша проблема, з якою боролися дослідники в 1960-х роках?

Для проблем у NP «наскільки це важко?» зазвичай досить легко відповісти, але MCSP здається дивним викидом. «У нас дуже мало проблем, які «ширяють», які не були б пов’язані з цим острівком NP-complete проблем, навіть якщо вони здаються складними», — сказав Кабанець.

Кабанець знав, що вони з Цаєм не перші розглядають проблему, яку вони охрестили MCSP. Радянські математики вивчали дуже подібну проблему, починаючи з 1950-х років, у першій спробі зрозуміти внутрішню складність різних обчислювальних задач. Леонід Левін боровся з цим, розробляючи те, що стане теорією NP-повноти наприкінці 1960-х років, але він не зміг довести, що це NP-повнота, і він опублікував свою фундаментальну статтю без неї.

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

«У певному сенсі це мета-мета-складність», — сказав Рахул Сантанам, теоретик складності в Оксфордському університеті.

Але чи була це твердість повністю вниз, чи був принаймні якийсь спосіб зрозуміти, чому дослідникам не вдалося довести, що MCSP є NP-повним? Кабанець виявив, що так, була причина: складність розуміння складності схеми діє як перешкода для будь-якої відомої стратегії доведення NP-повноти MCSP — проблема, яка сама по собі пов’язана з труднощами розуміння складності схеми. Зікручена, згубна логіка бар’єру природних доказів здавалася неминучою.

Також можливо, що MCSP не є NP-повним, але це також здається малоймовірним — деякі простіші варіанти проблеми вже відомі як NP-повні.

«Ми просто не маємо гарного місця, щоб розмістити це, яке безпосередньо пов’язує це з усіма іншими проблемами, які ми вивчаємо», — сказав Імпальяццо.

Кабанець висвітлив дивну поведінку MCSP, але не знав, як рухатися далі. Дослідження метаскладності сповільнилося до краплі. Через 16 років він знову процвітав, коли дослідники виявили дивовижний зв’язок з іншим фундаментальним питанням: наскільки важко вирішувати проблеми, якщо більшість часу дбати лише про правильну відповідь?

Війна світів

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

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

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

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

«Щоб досягти успіху в Радянському Союзі як молодий дослідник, ви не могли бути дуже самовпевненим, і важко уявити, щоб Леонід не був самовпевненим», — сказав Імпальяццо.

Левін емігрував до Сполучених Штатів у 1978 році, а в середині 1980-х років звернув увагу на середню складність випадків. Він почав працювати з іншими над подальшим розвитком теорії, включаючи Імпальяццо, який на той час був аспірантом. Але навіть коли вони досягли прогресу, Імпальяццо виявив, що дослідники часто говорять повз один одного. Він хотів зібрати всіх на одну сторінку, і йому не допомогло те, що документи Левіна були славнозвісними лаконічними — тим, що ініціював поль середньої складності склав менше двох сторінок.

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

Команда папір, опублікований у 1995 році, миттєво став класикою. Імпальяццо придумав химерні назви п'ять світів відрізняються різним ступенем обчислювальної жорсткості та різними криптографічними можливостями. Ми живемо в одному з цих світів, але не знаємо в якому.

З тих пір, як з’явилася стаття Імпальяццо, дослідники мріяли усунути частини його мініатюрного мультивсесвіту — звузити простір можливостей, довівши, що деякі світи все-таки неможливі. Два світи є особливо спокусливими цілями: ті, де криптографія неможлива, навіть якщо P ≠ NP.

В одному з цих світів, який називається Евристика, усі NP-повні проблеми легко розв’язати на більшості вхідних даних, але швидкі алгоритми час від часу допускають помилки, тому ці проблеми все ще вважаються складними за стандартами теорії складності найгіршого випадку. Це світ, у якому криптографія неможлива, оскільки майже кожен код легко зламати. В іншому світі, який називається Пессіленд, криптографія неможлива з іншої причини: кожна проблема складна в середньому розумінні, але шифрування повідомлення робить його нерозбірливим навіть для одержувача.

Ці два світи виявилися тісно пов’язаними з проблемами мета-складності — зокрема, доля Heuristica пов’язана з давнім питанням про те, чи є MCSP NP-повним. Питання, яке так давно захоплювало Кабанця і спантеличило Левіна, не просто курйоз: на кону цілий світ.

Щоб виключити Евристику, дослідникам довелося б зруйнувати різницю між найгіршою та середньою складністю, тобто довести, що будь-який гіпотетичний алгоритм, який правильно розв’язує NP-повну проблему на більшості вхідних даних, може її вирішити. у всіх випадках. Відомо, що такий тип зв’язку, який називається редукцією від найгіршого до середнього випадку, існує для певних проблем, але жодна з них не є NP-повною, тому ці результати не означають нічого більш загального. Усунення Heuristica займе криптографів на півдорозі до здійснення мрії про безпечне шифрування, засноване на єдиному припущенні, що P ≠ NP.

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

Дослідникам доведеться знайти інший підхід, і тепер вони вважають, що MCSP може бути саме тією проблемою, яка їм потрібна. Але це не стане ясним протягом більше десяти років. Перший проблиск зв’язку з’явився в результаті постійного захоплення Марко Кармозіно природним доказовим бар’єром.

Кармозіно вперше зіткнувся з дослідженням мета-складності, будучи аспірантом через a Папір 2013 Кабанцем та чотирма іншими дослідниками, які розвинули підхід до природного доказового бар’єру, який Кабанець започаткував понад десять років тому. Це лише зміцнило його переконання, що з класичної статті Разборова та Рудіча можна ще більше повчитися.

«У той час я був одержимий цією газетою», — сказав Кармозіно. "Нічого не змінилось."

Одержимість нарешті принесла плоди під час візиту на семестровий семінар в Каліфорнійському університеті в Берклі, де він проводив більшу частину свого часу, спілкуючись з Імпальяццо, Кабанцем і Антоніна Колоколова, теоретик комплексності з Меморіального університету Ньюфаундленду, який співпрацював з Кабанцем над статтею 2013 року. Кармозіно вже працював з ними трьома раніше, і ця успішна співпраця додала йому впевненості задавати їм запитання про тему, яка його найбільше захоплювала.

«Він по-хорошому набридав людям», – згадує Кабанець.

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

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

«Не було очевидно, що такий зв’язок взагалі існуватиме», — сказав Імпальяццо.

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

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

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

Результат привернув увагу теоретиків складності, які працювали над іншими темами. Це також був попередній перегляд подальших зв’язків між метаскладністю та складністю середнього випадку, які виникнуть протягом наступних років.

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

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

Частковий кредит

За роки, відколи Кармозіно та його колеги опублікували свою статтю, прогрес лише прискорився.

«Відбуваються нові речі», - сказала Колоколова. «Є багато дійсно, дуже яскравих молодих дослідників».

Іланго є одним із цих молодих дослідників — у перші три роки навчання в аспірантурі він атакував складну відкриту проблему доведення NP-повноти MCSP за допомогою двосторонньої стратегії: доведення NP-повноти для простий версії MCSP, як це робили дослідники складності схеми, атакуючи P проти NP у 1980-х роках, одночасно доводячи NP-повноту для більш складні версії, які інтуїтивно здаються складнішими, і тому їх, можливо, легше довести.

Іланго приписує свій інтерес до мета-складності Ерік Аллендер, теоретик комплексності з Ратгерського університету та один із небагатьох дослідників, які продовжували працювати над метаскладністю у 2000-х і на початку 2010-х років. «Його ентузіазм був заразливим», — сказав Іланго.

Ще один молодий дослідник, надихнутий Аллендером Шуїчі Хірахара, нині професор Національного інституту інформатики в Токіо. Ще будучи аспірантом у 2018 році, Хірахара розкрив справжній ступінь зв’язку між метаскладністю та складністю середнього випадку, який виявили Кармозіно та його співавтори. Ці чотири дослідники виявили зв’язок між середньою складністю однієї проблеми — MCSP — і найгіршою складністю іншої — булевим навчанням. Хірахара розвинув їх техніку далі дрейф від найгіршого до середнього випадку для MCSP. Його результат означає, що гіпотетичний середній алгоритм MCSP, як той, який розглядали Кармозіно та його колеги, насправді буде достатньо потужним, щоб розв’язати дещо іншу версію MCSP без жодних помилок.

Результат Хірахари є захоплюючим, оскільки багато дослідників підозрюють, що MCSP є NP-повним, на відміну від усіх інших проблем, для яких відомі скорочення від найгіршого до середнього випадку. Якщо вони зможуть розширити результати Хірахари, щоб охопити всі алгоритми середнього випадку, а потім довести, що MCSP є NP-повним, це доведе, що ми не живемо в Heuristica.

«Це був би справді приголомшливий результат», — сказав Сантанам.

Довести, що MCSP є NP-повним, може здатися важким завданням — зрештою, це питання було відкритим понад 50 років. Але після а прорив минулого року Хірахара, дослідники тепер набагато ближче, ніж хтось очікував кілька років тому.

Хірахара довів NP-повноту для варіанту проблеми під назвою частковий MCSP, у якому ви ігноруєте певні записи в кожній таблиці істинності. Його доказ ґрунтувався на методах, розроблених Іланго, щоб показати, що частковий MCSP був еквівалентним, здавалося б, непов’язаній проблемі, яка включає криптографічний метод, який називається обмін секретами. Це спосіб розділити зашифроване повідомлення між багатьма людьми, щоб його можна було розшифрувати, лише якщо певна частина з них працює разом.

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

Цей результат надихнув дослідників мета-складності навіть більше, ніж попередня робота Хірахари, і інші дослідники також звернули увагу — теоретик складності та блогер Ленс Фортноу назвав це підсумок року. Це тому, що вирішення таких версій обчислювальних проблем із «частковою функцією» було ключовим проміжним кроком в інших доказах NP-повноти.

«Це чудова робота, — сказав Вільямс. «Усі вважали, що ці часткові проблеми були приблизно такими ж складними, як повна проблема».

Залишаються перешкоди для підтвердження NP-повноти для повної версії MCSP. Але жодна з перешкод не свідчить про те, що потрібен абсолютно новий інструментарій — це може бути просто питанням пошуку правильного способу поєднання відомих методів. Доказ нарешті вирішив би статус однієї з небагатьох проблем, які чинили опір класифікації протягом усього часу існування теорії складності. В електронному листі Левін написав: «Мені було б принизливо показати, що я був дурним, якщо не зміг цього побачити :-)».

Відсутні частини

MCSP – навіть не єдина проблема метаскладності, яка стала поштовхом до серйозного прориву. У 2020 році криптограф Cornell Tech Перевал Рафаеля та його аспірант Яньі Лю виявив зв'язок між іншою проблемою мета-складності та фундаментальним криптографічним протоколом, який визначає межу між Heuristica та Pessiland, найгіршим зі світів Impagliazzo (де NP-повні проблеми складні в середньому сенсі, але криптографія все ще неможлива). Це робить проблему, яку вони вивчали, головним кандидатом для нападу на Песіленд і їх новіша робота вказує на те, що він також може працювати проти Heuristica.

«Відсутні різні частини головоломки», — сказав Пасс. «Для мене просто чарівно, що ці поля настільки тісно пов’язані».

Хірахара попереджає, що на дослідників, які мають намір знищити світи, створені Імпальяццо 30 років тому, ще чекають проблеми. «Я хотів би сказати, що в якийсь момент Heuristica і Pessiland будуть виключені, але я не впевнений, наскільки ми близько», — сказав він.

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

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

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

«Насправді чудово, що це так важко», — сказав Кармозіно. «Мені ніколи не буде нудно».

Примітка редактора: Скотт Ааронсон є членом Журнал QuantaАвтора Консультативна рада.