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

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

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

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

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

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

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

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

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

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

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