Простая проблема приводит к тому, что числа слишком велики для нашей Вселенной | Журнал Кванта

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

Это звучит достаточно просто. «Вы можете пойти в начальную школу и рассказать об этом детям», — сказал Кристоф Хаазе, ученый-компьютерщик из Оксфордского университета. «Люди подумают: «Это должно быть легко».

Но математическая проблема, лежащая в основе дилеммы Алисы, называемая проблемой достижимости для систем сложения векторов, на удивление тонкая. Хотя некоторые случаи можно легко решить, ученые-компьютерщики почти полвека боролись за полное понимание проблемы. Теперь, благодаря серии прорывов, произошедших за последние несколько лет, они твердо установили, насколько сложной может стать эта проблема.

Оказывается, эта детская проблема абсурдно, почти карикатурно сложна — настолько сложна, что практически все остальные известные сложные вычислительные задачи выглядеть, ну, детской игрой. Попробуйте количественно оценить усилия, необходимые для решения этой проблемы, и вскоре вы столкнетесь с такими большими числами, что даже подсчитав их цифры, вы сможете получить числа, о которых вы никогда не слышали. Такие цифры часто вызывают сравнения с масштабами Вселенной, но даже эти аналогии не соответствуют действительности. «Это было бы несправедливо», — сказал Георг Цецше, ученый-компьютерщик из Института программных систем Макса Планка в Кайзерслаутерне, Германия. «Вселенная такая маленькая».

В пределах досягаемости?

Вкратце, проблема достижимости касается математических объектов, называемых векторами, которые представляют собой упорядоченные списки чисел. Элементы этих списков называются компонентами, а количество компонентов вектора называется его размерностью. Например, запас фруктов Алисы можно описать четырехмерным вектором (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$ переходов, подразумевая новую нижнюю границу, которая затмила липтоновскую. Но какой бы головокружительной ни была тетрация, это еще не последнее слово о сложности проблемы.

К Квинквагинтиллиону и далее 

Всего через несколько месяцев после шокирующего нового нижнего предела сложности достижимости 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», — посоветовал Хавьер Эспарса, ученый-компьютерщик Мюнхенского технического университета.

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

Последний прорыв произошел в 2021 году, когда Червинский консультировал студента второго курса по имени Лукаш Орликовский. Он поручил Орликовскому простой вариант задачи, чтобы тот быстрее освоился, и работа Орликовского помогла им двоим разработать новую технику, которая также применима к общей проблеме достижимости. Это позволило им поднять нижнюю границу существенно — вплоть до верхней границы Аккермана Леру и Шмитца. Работая независимо, Леру получил эквивалентный результат Примерно в то же время.

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

Никогда не заканчивал

Исследователи продолжили изучение проблемы достижимости VAS после определения ее точной сложности, поскольку многие варианты вопроса остаются без ответа. Например, верхняя и нижняя границы Аккермана не различают разные способы увеличения n, например, увеличение размерности векторов или увеличение количества разрешенных переходов.

Недавно Червинский и его коллеги добился прогресса выявление этих различных эффектов путем изучения того, как быстро может увеличиваться сложность вариантов систем сложения векторов с фиксированной размерностью. Но предстоит сделать еще больше — даже в трех измерениях, где системы сложения векторов легко визуализировать, точная сложность проблемы достижимости остается неизвестной.

«В каком-то смысле нам это просто неловко», — сказал Мазовецкий.

Исследователи надеются, что лучшее понимание относительно простых случаев поможет им разработать новые инструменты для изучения других моделей вычислений, которые более сложны, чем системы сложения векторов. В настоящее время мы почти ничего не знаем об этих более сложных моделях.

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

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