[Перевод] Простая проблема приводит к слишком большим числам для нашей Вселенной26.12.2023 11:15

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

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

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

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

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

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

Вкратце проблема достижимости касается математических объектов, называемых векторами, которые представляют собой упорядоченные списки чисел. Элементы этих списков называются компонентами, а количество компонент вектора называется его размерностью. Например, запас фруктов Алисы можно описать четырехмерным вектором (a, b, c, d), компоненты которого представляют, сколько яблок, бананов, дынь и апельсинов у неё есть в любой момент времени.

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

«Это очень естественное ограничение для модели реальности», — сказал Войцех Червинский, учёный из Варшавского университета. «У вас не может быть отрицательного количества яблок».

В некоторых системах легко определить, достижим ли целевой вектор. Но это не всегда так. Учёные больше всего интересуются простыми на вид системами сложения векторов, в которых не очевидно, насколько сложно определить достижимость. Чтобы изучить эти случаи, исследователи начинают с определения числа, которое количественно характеризует размер данной системы. Это число, представленное буквой n, включает в себя количество измерений, количество переходов и другие факторы. Затем они задаются вопросом, насколько быстро может возрастать сложность проблемы достижимости по мере увеличения n.

Чтобы ответить на этот вопрос, исследователи используют два взаимодополняющих подхода. Во-первых, они ищут примеры особенно сложных систем сложения векторов, в которых определение достижимости требует некоторого минимального уровня усилий. Эти минимальные уровни называются «нижними границами» сложности задачи — они говорят исследователям: «Самые сложные системы для данного n по меньшей мере настолько сложны».

Во-вторых, исследователи пытаются установить «верхние границы» — пределы того, насколько трудной достижимость может быть даже в самых дьявольских системах. Они говорят: «Самые сложные случаи для данного n не более чем настолько сложны». Чтобы точно определить, насколько трудна достижимость в самых сложных системах, исследователи пытаются сдвигать нижние границы вверх и верхние границы вниз, пока они не совпадут.

Материал из кошмаров

Системы сложения векторов имеют долгую историю. С 1960-х годов учёные использовали их для моделирования программ, которые разбивают вычисления на множество небольших частей и работают над ними одновременно. Этот вид «параллельных вычислений» сейчас распространен повсеместно, но исследователи до сих пор не до конца понимают его математические основы.

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

Затем Липтон доказал, что может построить систему размера n, в которой кратчайший путь между двумя состояниями включает более $2^{2^{n}}$ переходов. Это подразумевало соответствующую двойную экспоненциальную нижнюю границу усилий, необходимых для определения достижимости в его системах. Это было поразительное открытие: двойной экспоненциальный рост — кошмар компьютерных учёных. Действительно, исследователи часто отказываются даже от обычного экспоненциального роста, который меркнет по сравнению с ним: $2^{5} = 32$ , но $2^{2^{5}}$ — это более 4 миллиардов.

Войцех Червинский помог доказать, насколько сложно определить, можно ли перейти от одной точки к другой в определенных математических системах.

Большинство исследователей считали, что Липтон придумал самую сложную из возможных систем сложения векторов, а это значит, что он поднял нижнюю границу настолько высоко, насколько это было возможно. Единственное, чего не хватает в этом случае, — это верхней границы, то есть доказательства того, что не может быть системы, в которой определение достижимости было бы ещё сложнее. Но никто не знал, как это доказать. Учёный Эрнст Майр подошел к ответу ближе всего, когда в 1981 году доказал, что в принципе всегда возможно определить достижимость в любой системе сложения векторов. Но его доказательство не установило какой-либо количественной верхней границы сложности проблемы. Пол был, но потолка не было заметно.

«Я, конечно, время от времени думал об этом», — сказал Липтон. «Но через некоторое время я сдался, и, насколько я мог судить, никто не добился никакого прогресса в течение примерно 40 лет.»

В 2015 году учёные Жером Леру и Сильвен Шмитц наконец установили количественную верхнюю границу — настолько высокую, что исследователи предположили, что это всего лишь первый шаг, который можно опустить вниз, чтобы достичь нижней границы Липтона.

Но произошло нечто иное. В 2019 году исследователи обнаружили, что нижняя граница намного выше, чем у Липтона, и это перевернуло десятилетия общепринятого мнения. Проблема достижимости VAS оказалась гораздо более сложной, чем кто-либо ожидал.

Башня из степеней

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

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

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

Тетрация — это прямое расширение шаблона, соединяющего наиболее знакомые математические операции, начиная со сложения. Сложите n копий числа, и результат будет эквивалентен умножению этого числа на n. Если вы умножаете n копий числа, это эквивалентно экспоненциации или возведению числа в n-ную степень. Тетрация, часто изображаемая парой стрелок, направленных вверх, является следующим шагом в этой последовательности: тетрирование числа на n означает возведение его в степень n раз, чтобы создать башню степеней высотой в n этажей.

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

В своем знаковом результате Червинский и его коллеги доказали, что существуют системы сложения векторов размера n, в которых лучший способ определить достижимость — это проложить путь, включающий более $2\uparrow \uparrow n$ переходов, подразумевая новую нижнюю границу, затмившую липтоновскую. Но какой бы головокружительной ни была тетрация, это ещё не последнее слово о сложности проблемы.

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

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

Чтобы понять эту функцию, доведите до мрачного завершения шаблон, используемый для определения тетрации. Следующая операция в последовательности, называемая пентацией, представляет собой повторную тетратацию; за ней следует еще одна операция (гексация) для повторной пентации и так далее.

Функция Аккермана, обозначаемая A(n) — это то, что вы получаете, перемещаясь на один шаг вверх по этой лестнице операций с регулярной остановкой на числовой прямой: A(1)=1+1 , $A(2)=2\times 2$ , $А(3)=3^{3}$ , $А(4)=4\uparrow \uparrow 4=4^{4^{4^{4}}}$ и так далее. Число цифр в A(4) само по себе является колоссальным числом, примерно равным 1 квинвигинтиллиону — это причудливое и редко используемое название для единицы, за которой следуют 153 нуля. «Не беспокойтесь о функции Аккермана от 5», — посоветовал Хавьер Эспарса, учёный из Технического университета Мюнхена.

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

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

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

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

Не заканчивая

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

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

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

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

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

Автор перевода @arielf

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.