A metamatematika új szerepe
Különösen fontos kiemelni, hogy a kutatók egyre többször vizsgálják, vajon miért nem tudnak hatékonyabban bizonyítani ilyen „nehéz” problémákat. A metamatematika, vagyis maga a bizonyítások hátterének elemzése, megvizsgálja azokat az alapfeltevéseket, amelyek minden bizonyítás kiindulópontjai. Ha változtatnak az axiómákon, gyakran kiderül, egyes tételek bizonyításához mennyi és milyen matematikai alapra van szükség. Ez ma már a számításelméleti nehézség vizsgálatának kulcsa: mit lehet, és mit nem lehet ténylegesen bizonyítani különböző axiómakészletekből kiindulva.
Nem sokkal később újabb csavar következett: három kutató fordított szemléletet választott. Olyan módszert alkalmaztak, amit fordított matematikának (reverse mathematics) hívnak: nem a szokásos axiómákból próbáltak meg tételt levezetni, hanem cserélték a szerepeket, és egy bizonyítás tárgyát emelték axióma rangjára, majd ezt próbálták igazolni. Így sikerült kimutatniuk, hogy számos számításelméleti tétel szorosan – sőt, pontosan – ekvivalens egymással.
A skatulyaelv meglepő ereje
Kevesen gondolnák, hogy a bonyolult problémák bizonyításának kulcsa lehet egy triviálisnak tűnő elv, mint a skatulyaelv (pigeonhole principle): ha több galambot próbálunk kevesebb lyukba helyezni, legalább egy lyukban több galamb lesz. Ez az egyszerű megállapítás számos komplex bizonyítás alapkövévé vált.
Kezdetben a kutatók arra voltak kíváncsiak, hogyan lehet a kommunikációs komplexitáselmélet egyik alapkérdését – például annak eldöntését, hogy két fél egy-egy bináris sorozata megegyezik-e – a lehető legkevesebb információcserével megoldani. Régóta ismert, hogy elkerülhetetlenül annyi bitet kell továbbítani, amilyen hosszú maga a sorozat. Ezt korábban rendszerint a skatulyaelvvel bizonyították. Újszerű gondolatként azonban felmerült: talán maga a kommunikációhoz szükséges minimális bitmennyiség kimondása is éppen olyan erőteljes, mint a skatulyaelv, és fordítva – azaz egymásból is levezethetők.
Ekvivalenciák hálója
A kutatók – Chen, Li és Oliveira – egy szűkebb, de fontos axiómakészletet (PV1) választottak, mely képes pár alapvető számításelméleti tételt önmagában is bizonyítani. Ha ehhez még hozzávesznek egy speciális skatulyaelvet, már igazolható a kommunikációs tétel is. Hamar sikerült kimutatni, hogy a két eredmény szinte teljesen egymásra vezethető vissza: vagyis ebben az axiómarendszerben tökéletesen ekvivalensek.
De itt nem álltak meg: kiderült, hogy a fordított matematika módszere sokkal szélesebb körben alkalmazható. Például sikerült kimutatni, hogy a skatulyaelv ugyanannyira alapvető, mint az a híres tétel, amely kimondja: egy egyszerű elméleti számítógép minimálisan mekkora idő alatt dönti el egy bitsorozatról, hogy palindróm-e (visszafelé olvasva is ugyanaz). Különösen fontos kiemelni, hogy első ránézésre a skatulyaelv – egy egyszerű számlálási elv – és a palindróm-felismerési időre vonatkozó tétel között semmi tartalmi kapcsolatot nem feltételeznénk. Mégis, most kiderült, hogy valójában teljesen egyenértékűek ebben a logikai rendszerben.
A bizonyíthatóság határai
Ez az ekvivalenciaháló nem csak az elméleti kutatások között teremt új kapcsolatokat, hanem azt is megmutatja, meddig terjed a PV1 axiómakészlet bizonyíthatósága. A kortárs eredmények egyértelművé teszik: a skatulyaelv nem bizonyítható pusztán PV1-ből – és emiatt azok a tételek sem, amelyek szorosan ehhez az elvhez kapcsolódnak.
Nem sokkal később újabb felismerés született: a fordított matematika kiválóan feltárja, milyen rejtett összefüggések bújnak meg a már ismert bizonyítások között, még ha a teljes megoldatlanság területére egyelőre nem is vezet el bennünket.
Új korszak a metamatematikában
A metamatematika térnyerése látványos: egyre több, eddig háttérbe szorult bizonyítási módszer és logikai elemzés kap helyet a modern matematikai kutatásokban, különös tekintettel az MI és a számításelmélet határterületein. Az új generációs kutatók, mint Li és társai, friss perspektívával közelítenek a régen megoldatlannak tartott kérdésekhez. A vonzó gondolat: ha elakadtunk az egyik úton, talán érdemes visszalépni, és az alapoktól újraépíteni a tudásrendszert.
Az eredmények tanulsága: sok, elsőre szűk jelentőségűnek tűnő tétel jóval alapvetőbb, mint gondoltuk, és maguk a bizonyítási módszerek is alkalmasak lehetnek új szintű matematikai önvizsgálatra. Az MI által felvetett bonyolult problémák nehézségének megértéséhez tehát nem csupán új algoritmusok, hanem új matematikai szemlélet is kell.
