Проблема, яка звучить легко, дає надто великі числа для нашого Всесвіту | Журнал Quanta

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

Звучить досить просто. «Ви можете піти в початкову школу і розповісти [це] дітям», — сказав Крістоф Гаазе, фахівець з інформатики в Оксфордському університеті. «Люди подумають: «Це повинно бути легко».

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

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

В межах досяжності?

Якщо розібратися по суті, проблема досяжності стосується математичних об’єктів, званих векторами, які є впорядкованими списками чисел. Записи в цих списках називаються компонентами, а кількість компонентів у векторі називається його розмірністю. Фруктовий інвентар Аліси, наприклад, можна описати чотиривимірним вектором (a, b, c, d), компоненти якого представляють, скільки яблук, бананів, дині та апельсинів вона має в будь-який момент часу.

Система додавання векторів, або VAS, — це набір векторів, що представляють можливі переходи між станами в системі. Для Аліси вектор переходу (−1, −1, 1, 0) представлятиме обмін яблука та банана на диню. Проблема досяжності VAS запитує, чи існує будь-яка комбінація дозволених переходів, яка може перевести вас із певного початкового стану в певний цільовий стан, або, математично кажучи, чи існує якась сума векторів переходу, яка перетворює початковий вектор у цільовий вектор. Є лише одна заковика: жодна складова вектора, що описує стан системи, ніколи не може опускатися нижче нуля.

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

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

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

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

Кошмари

Системи векторного додавання мають довгу історію. Починаючи з 1960-х років комп’ютерні вчені використовували їх для моделювання програм, які розбивають обчислення на безліч дрібних частин і працюють над ними одночасно. Цей вид «паралельних обчислень» зараз поширений всюди, але дослідники досі не повністю розуміють його математичні основи.

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

Тоді Ліптон доведений він міг побудувати систему розмірів n у якому найкоротший шлях між двома станами включав більше $latex 2^{2^n}$ переходів. Це означало відповідну подвійну експоненціальну нижню межу зусиль, необхідних для визначення досяжності в його системах. Це було вражаюче відкриття — подвійне експоненціальне зростання — кошмар комп’ютерників. Дійсно, дослідники часто заперечують навіть звичайне експоненціальне зростання, яке блідне в порівнянні: $latex {2^5}= 32$, але $latex 2^{2^5}$ становить понад 4 мільярди.

Більшість дослідників вважали, що Ліптон створив найскладнішу можливу систему додавання векторів, тобто він підняв нижню межу настільки високо, наскільки це можливо. Єдине, чого не вистачає в такому випадку, — це верхня межа, яка б ішла разом із цим, тобто доказ того, що не може існувати система, у якій визначення досяжності було б ще важчим. Але ніхто не знав, як це довести. Інформатик Ернст Майр підійшов найближче, коли він доведений у 1981 році, що в принципі завжди можливо визначити досяжність у будь-якій системі додавання векторів. Але його доказ не встановив жодної кількісної верхньої межі того, наскільки важкою може бути проблема. Підлога була, але стелі не було видно.

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

У 2015 році інформатики Жером Леру та Сільвен Шмітц нарешті встановлено кількісна верхня межа — такий високий, що дослідники припустили, що це лише перша сходинка, яку можна було зрушити до нижньої межі Ліптона.

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

Вежа сил

Шокуючий результат 2019 року став результатом провалу. У 2018 році Червінський спростував гіпотезу Леру та Філіп Мазовецький, фахівець з інформатики, який зараз працює у Варшавському університеті, це допомогло б досягти прогресу у подібній проблемі. У подальших дискусіях дослідники знайшли багатообіцяючий новий спосіб побудови надзвичайно складних векторних систем додавання, що могло б означати нову нижню межу проблеми досяжності VAS, у якій прогрес так довго зупинявся.

«Усе, що в моїй голові пов’язане з досяжністю VAS», — згадував Червінскі. Протягом семестру з невеликим викладацьким навантаженням він вирішив зосередитися виключно на цій проблемі разом з Леру, Мазовецьким та двома іншими дослідниками: Славомір Ласота Варшавського університету і Ранко Лазіч університету Уоріка.

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

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

Важко уявити, як швидко тетрація виходить з-під контролю: $latex 2 uparrowuparrow 3$, або $latex 2^{2^2}$, становить 16, $latex 2 uparrowuparrow 4$ — трохи більше 65,000 2, а $latex 5 uparrowuparrow 20,000$ — це число з майже 2 6 цифр. Фізично неможливо записати всі цифри $latex XNUMX uparrowuparrow XNUMX$ — це обмеження життя в такому маленькому всесвіті.

У своєму знаковому результаті Червінскі та його колеги довели, що існують векторні системи додавання розміру n де найкращий спосіб визначити досяжність — це намітити шлях, що включає більше $latex 2 uparrowuparrow n$ переходів, що передбачає нову нижню межу, яка затьмарює Ліптона. Але хоч би тетрація крутила голову, це ще не остаточне слово щодо складності проблеми.

До Quinquagintillion і далі 

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

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

Функція Аккермана, позначена як $latex A(n)$, — це те, що ви отримуєте, коли просуваєтесь на одну сходинку вгору за цією драбиною операцій із кожною зупинкою на числовій прямій: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$ і так далі. Кількість цифр у $latex A(4)$ сама по собі є колосальним числом, яке приблизно дорівнює 1 квінквагінтильйону — це химерна та рідко потрібна назва для 1, за якою слідують 153 нулі. «Не турбуйтеся про Ackermann of 5», — порадили Хав'єр Еспарза, фахівець з інформатики в Технічному університеті Мюнхена.

Результат Леру та Шмітца залишив великий розрив між нижньою та верхньою межами — точна складність проблеми досяжності VAS могла лежати на будь-якому кінці діапазону або десь посередині. Червінський не мав наміру залишати цей розрив. «Ми продовжували працювати над цим, тому що було зрозуміло, що це найбільша річ, яку ми коли-небудь робили в своєму житті», — сказав він.

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

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

Ніколи не закінчено

Дослідники продовжили вивчення проблеми досяжності VAS після визначення її точної складності, оскільки багато варіантів питання залишаються без відповіді. Верхня та нижня межі Аккермана, наприклад, не розрізняють різні способи збільшення n, наприклад збільшення розмірності векторів або збільшення кількості дозволених переходів.

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

"У певному сенсі це просто соромно для нас", - сказав Мазовецький.

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

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

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