Едно и също нещо ли са пътуващият търговец и принципът на Дирихле? Реверсивната математика обърна фактите с главата надолу и показа скритата форма на Вселената

Някои истини не могат по принцип да бъдат доказани: математиците откриха границите на собствената си реалност.

От няколко десетилетия изследователите, изучаващи теорията на изчислителната сложност, се опитват да докажат стриктно това, което изглежда интуитивно очевидно: има задачи, които просто не се поддават на ефективните алгоритми. Често пример за това е задачата за пътуващия търговец, която изисква да се намери най-краткият маршрут, който преминава през набор от градове точно веднъж. При малки входни данни тази игра изглежда безобидна, но с нарастването на броя на точките всички алгоритми започват да се „пропукват“ под собствената си изчислителна тежест. Специалистите са сигурни, че в този случай няма скрито бързо решение, но все още не е завършено математическото доказателство на тази увереност.

И на фона на тези трудности нараства интересът към добрата стара метаматематика – област, която изследва самите математически доказателства и аксиомите, на които те се базират. Логиците се опитват да разберат не само какви твърдения могат да бъдат изведени, но и къде са границите на самата система за разсъждение. В теорията на сложността това е особено важно: ако дадено твърдение по принцип не следва от избраните аксиоми, липсата на доказателство вече не е загадка – тя се превръща в свойство на математическата вселена, в която работят изследователите. Затова учените преразглеждат наборите от аксиоми и проверяват какви резултати са постижими при различни отправни точки.

В неотдавнашната си научна работа трима изследователи са използвали подход, известен като „обратна математика“ или „реерсивна математика“. Той обръща обичайния ред: вместо да вземат аксиоми и да доказват теорема, те заместват самата теорема с аксиома и проверяват дали първоначалното твърдение може да бъде изведено от нея. Този обрат им даде възможност да покажат, че редица резултати от теорията на сложността, които на пръв поглед не са свързани помежду си, всъщност имат една и съща логическа сила в рамките на избраната система. Това само по себе си е необичайно: рядко се случва твърдения от различни области да си пасват толкова точно.

Идеята се заражда при Лиджи Чен, който през лятото на 2022 г., докато завършва дисертацията си и решава да посвети време на метаматематиката. Той насочва вниманието си към проблем от комуникационната сложност – област, която изучава колко информация трябва да обменят двама участници, за да решат съвместна задача. Един от класическите примери е определянето на равенството на два битови низа при зададен минимален брой съобщения, които трябва да бъдат предадени. Отдавна е известно, че естеството на този проблем не може да бъде измамено: за да проверим съответствието, трябва да изпратим толкова битове, колкото съдържа низът. Това се нарича долна граница, твърда граница, под която никой протокол не може да слезе.

Всички известни доказателства за тази долна граница се основават на принципа на Дирихле, фундаменталното твърдение, че набор от обекти не може да бъде равномерно разпределен в по-малко клетки, без да се повтаря. Въпреки че този принцип изглежда като ученическа очевидност, той играе огромна роля в комбинаториката и теорията на сложността. Чен забелязал, че връзката между проблема за равенството и принципа на Дирихле може да работи и в двете посоки: ако е лесно да се изведе долна граница от принципа, то не би ли било възможно, напротив, да се изведе самият принцип, като се вземе долната граница като начална предпоставка?

Заедно с Джиату Ли той започва да работи в логическата система PV1 – слаба, но удобна платформа за анализ на връзките между теоремите. Те успяват да покажат, че долната граница за задачата за равенство и принципът на Дирихле имат една и съща логическа сила в рамките на тази система: като се вземе едното твърдение за дадено, може да се изведе другото. След като обсъждат това с Игор Оливейра от Университета в Уоруик, изследователите стигат до заключението, че подобни връзки могат да съществуват и между други резултати от теорията на сложността. Те започнали да проверяват такива хипотези една по една и открили много неочаквани еквивалентности.

Най-поразителният пример се оказа връзката между принципа на Дирихле и теоремата за минималното време, необходимо на еднолентова машина на Тюринг да провери дали даден низ е палиндром. Тези две области изглеждат несъизмерими: първото твърдение се отнася до чистото броене, а второто – до поведението на абстрактна изчислителна машина. Въпреки това, вътре в PV1 те изглеждат еквивалентни. Изненадата на изследователите се дължи именно на факта, че подобни твърдения обикновено се смятат за твърде „тесни“ и специфични, за да имат фундаментален статут.

Новата мрежа от еквивалентности помага не само да се проследят скритите връзки между твърденията, но и да се разберат ограниченията на самата система PV1. Ако принципът на Дирихле не може да бъде изведен без разширяване на аксиомите, то всички теореми, които се оказват логически еквивалентни на него, също са непостижими в рамките на PV1. Това само подсилва идеята, че опитите за доказване на фундаментални ограничения може да почиват не на уменията на математиците, а на ограниченията на самите логически основи, които те използват.

Възможностите на инверсната математика все още са далеч от решаването на основните загадки на теорията на сложността, но все повече изследователи виждат в нея шанс за излизане от задънената улица. Сред тях е Джиату Ли, който е завършил училище в Масачузетския технологичен институт и е написал подробно ръководство по метаматематика за специалисти по теория на сложността. Интересът към темата нараства и все повече учени са готови да преразгледат аксиомите, от които зависи съдбата на някои от най-известните нерешени проблеми на информатиката.