Lovász László

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

10. ábra

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 (10. ábra), a számítógéptudomány egyik megalkotója azon gondolkodott, hogy vajon hogyan lehet megkülönböztetni egy nagyon fejlett számítógépet egy embertől.

11. ábra

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 (11. ábra).

12. ábra

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 program van, ami automatizálja a címek létrehozását, hogy aztán hirdetéseket küldjön szét róluk, vagy ami 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 nincs az a nagy előnye, 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. 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.