Lovász László matematikus Mindentudás Egyeteme előadásának (2003) első része itt, második része itt olvasható.

IV. A bizonyítás új fogalma

A bizonyítás a matematika lelke, a görög tudomány talán legfontosabb alkotása. Mégis, az iskolai matematikatanításból sokszor kimarad. Még egyetemi hallgatók is gyakran nem értik, miért van rá szükség: „Elhisszük mi a tanár úrnak, minek azt bizonygatni.'' (Remélem, ez csak amerikai tapasztalatom.)

A Pitagorasz-tételre már nagyon-nagyon sok bizonyítást talált az emberiség, és világos, hogy a bizonyításon nem azért kell végigmenni, hogy a tétel helyességéről még jobban meg legyünk győzve, hanem azért, hogy a bizonyításban szereplő matematikai módszereket elsajátítsuk. A programok helyessége, a kommunikációs protokollok biztonsága azonban nap mint nap bizonyítást igényel(ne).   

1. Interaktív bizonyítás

Még érdekesebb azonban, hogy az infomatika a bizonyítás újszerű fogalmához is elvezet: az interaktív bizonyításhoz.

Alan Turing angol matematikus, a számítógéptudomány egyik megalkotója azon gondolkodott, vajon hogyan lehet megkülönböztetni egy nagyon fejlett számítógépet egy embertől. 

Azt a kísérletet javasolta, hogy egy szobába ültessünk be egy embert egy képernyővel és billentyűzettel, míg a másik szobába vagy egy másik embert ültessünk hasonló képernyővel és billentyűzettel, vagy egy számítógépet tegyünk. Az első ember kérdéseket tehet fel, vagy bármi egyéb módon társaloghat a másik szobában levő lénnyel, és el kell döntenie ennek alapján, hogy emberrel vagy géppel áll-e szemben. Ezt a kísérletet nevezik Turing-tesztnek. 

Hinnénk-e, hogy ezt a nyilvánvalóan csak gondolatkísérletnek szánt tesztet naponta sok ezerszer végzik el? Ha valaki például új e-mail címet akar csinálni magának, ilyesféle kérdéssel találkozhat: „Kérjük, gépelje be az alábbi betűket”, és kicsit piszkos alapon néhány kuszán odaírt betűt lát.

Ha valaki nem érti, mire való ez, rákattinthat a „Miért?” feliratra, és megtudja, hogy azért van erre szükség, mert sok az olyan program, amely automatizálja a címek létrehozását, hogy aztán hirdetéseket küldjön szét róluk, vagy ami még rosszabb, levelek tömeges küldésével megbénítson valakit. A képen az emberi szem könnyedén felismeri a betűket, de egy számítógépet (ma még legalábbis) a betűk torzulásai és a kusza vonalak megtévesztenek, így a programozott címgenerálást ki lehet szűrni.

Látszik tehát, hogy a mai számítógépek még nagyon gyorsan megbuknak a Turing-teszten, bár érdemes azt is megemlíteni, hogy itt a tesztet magát nem ember, hanem egy számítógép hajtja végre.

A fenti eljárás az interaktiv bizonyítás szép példája: két résztvevő van, és ebben az esetben a Bizonyító azt a „tételt” akarja bebizonyítani, hogy ő ember. A hagyományos matematikában a tételhez hozzá lehet csatolni a bizonyítást - itt azonban van egy Ellenőr, aki egy vagy több kérdést tesz föl, és a „bizonyítás” a kérdéstől függ. Ez a séma sokkal erősebb a hagyományos bizonyítási formáknál - gondoljunk csak bele, hogyan tudnánk kérdés nélkül bebizonyítani, hogy emberek vagyunk?

Érdemes azt is megjegyezni, hogy a séma ereje a kérdés (a kusza betűsorozat) véletlen voltán múlik. Ha mindenkitől ugyanazt kérdezné vagy akár csak előre kiszámítható kérdést tenne fel, könnyű volna egy számítógépet úgy programozni, hogy az a jó választ adja. A jó véletlen-generátor tehát ennek a protokollnak is elengedhetetlen része!

2. Elektronikus boríték

Hasonló interaktív bizonyítások lépten-nyomon előfordulnak - gondoljunk a jelszavakra, az „okos kártyákra” stb. Számítógépes hálózataink biztonsága nagyrészt az ilyen bizonyításokon múlik. Hadd mutassak be egy nagyon leegyszerűsített példát. Tegyük fel, hogy Aliz és Béla interneten keresztül sakkoznak. Beesteledett, és meg kell szakítani a mérkőzést. Hagyományos sakkversenyen ilyenkor az történik, hogy mondjuk Alíz eldönti az utolsó lépést, de nem teszi meg a táblán, hanem borítékolja és odaadja a bírónak. A borítékot Béla csak másnap nyithatja ki. Így egyikük sem ismeri a másik utolsó lépését, ezért nem jut ahhoz a nagy előnyhöz, hogy egész éjjel gondolkodhat a lépésén.

De most nincs bíró és nincs boríték. Alíz üzenhet valamit Bélának este, és megmondhatja a lépését másnap reggel, de mit üzenjen este? Ha már esti üzenetével elkötelezi magát, akkor Béla előnyben lesz; ha nem, akkor Alíz lesz előnyben, mert megváltoztathatja a lépést az éjjel folyamán. A hagyományos információelmélet szerint a „borítékolás” lehetetlen.

A bonyolultságelmélet azonban megoldást kínál. Előre megállapodnak abban, hogy a lépéseket egy-egy négyjegyű számmal írjak le: például Kf3 helyett azt mondják, hogy 9083. Ezek után Alíz választ magának két 100 jegyű prímszámot, amelyek közül a kisebbik úgy kezdődik, hogy 9083... (Láttuk, hogy számítógéppel nem nehéz ellenőrizni, hogy egy szám prímszám-e; be lehet bizonyítani a klasszikus matematika mély eszközeit felhasználva, hogy ha néhány száz 100 jegyű számot találomra kipróbál, ezek között lesz prím.) Legyen ez a két szám p és q, ahol p<q. Este Alíz elküldi a pq szorzatot Bélának, reggel pedig elküldi a két tényezőt (ami a boríték felbontásának felel meg).

Láthatjuk, hogy Béla már előző este megkapta a teljes információt: egy körülbelül 200 jegyű természetes számot, melynek a kisebbik prímtényezőjéből az első 4 jegy megadja Alíz lépését. De mivel a számot nem tudja hatékonyan tényezőire bontani, a lépést másnap reggelig (vagy akár évekig) nem tudja kiolvasni. Ezt a „titkot” hét pecsétként őrzi a számítási bonyolultság.

(Egyébként Béla jól teszi, ha ellenőrzi, hogy p és q tényleg prímek. Aki szeret logikai feladatokon eltöprengeni, belegondolhat, miért van erre szükség.)   Ennél sokkal bonyolultabb módon, de azért hasonló gondolatokat használva valósíthatók meg digitálisan a társadalmi érintkezés olyan fontos elemei, mint a mások által felbonthatalan boríték (titkosírás), elismervény, számla, aláírás és annak hitelesítése, vízjel stb.

V. Klasszikus kérdések új megvilágításban

A klasszikus matematikát sokan elefántcsonttoronynak látják. Godfrey Hardy, aki a prímszámok elméletének egyik legkiemelkedőbb kutatója volt a 20. század első felében, ezt írja Egy matematikus védekezése című könyvében:

Soha nem tettem semmi „hasznosat”. Semelyik felfedezésem sem volt közvetlenül vagy közvetve jó vagy rossz hatással a világ folyására, és nem valószínű, hogy valaha is hatással lesz... Az „igazi” matematikusok „igazi” matematikája, Fermat és Euler és Gauss és Abel és Riemann matematikája csaknem teljesen „haszontalan''.

Amikor az interneten vásárolunk vagy bankügyeket intézünk, számítógépünknek több száz jegyű számokról kell eldöntenie, hogy prímek-e - tizedmásodpercek alatt. Ehhez Fermat tételét használja. A különböző számítógépes protokollok, biztonsági módszerek a Hardy által felsorolt nagyságok szinte mindegyikének a munkájára építenek.

Ha azt kérdezzük, hogy melyik az a megoldatlan matematikai probléma, melynek a legnagyobb a gyakorlati jelentősége, azt hiszem, egyértelmű a válasz: Fel lehet-e egy mondjuk 1000 jegyű számot hatékonyan (nem-csillagászati idő alatt) prímtényezőire bontani?

Azt hiszem azonban, hogy ezek a tények Hardy kutatási elveit legalább annyira alátámasztják, mint amennyire az állításait cáfolják. Ha ezeket a nagyságokat csak kutatásuk közvetlen haszna motiválta volna és nem a matematikai kérdések szépsége, a megismerés vágya, akkor ma nem lennének eszközeink a számítógép-rendszerek biztonságának védelmére.