Mindentudás Egyeteme, 2003.

Lovász László matematikus előadásának első része itt olvasható.

2. Primtesztelés és -faktorizáció

Egy pozitív egész számot prímszámnak nevezünk, ha 1-en és önmagán kívül más egész számmal nem osztható. Az 1-et nem tekintjük prímnek, de utána aztán sok példát látunk: 2, 3, 5, 7, 11, 13 stb. Azokat a természetes számokat, melyek nem prímek, fel lehet bontani prímszámok szorzatára, például 6=2*3, 40=2*2*2*5 stb. - ezt a felbontást nevezzük prímfaktorizációnak.

A prímszámokkal kapcsolatban két fontos algoritmikus problémát fogalmazhatunk meg: ha adott egy k jegyű szám, hogyan tudjuk eldönteni róla, hogy prímszám-e; és ha nem prímszám, hogyan tudjuk megtalálni a prímtényezőit?

Mindkét kérdésre könnyű ”véges” választ adni: csak ki kell próbálni, hogy osztható-e a szám 2-vel, 3-mal, 4-gyel, 5-tel stb. Ha találunk olyan számot, amelyik osztója, akkor tudjuk, hogy nem prímszám, és a felbontást is könnyű megcsinálni. A baj ezzel az, hogy iszonyú sok számot kell kiprobálni: ahhoz, hogy egy 100 jegyű számról eldöntsük, hogy prím-e, 10¹⁰⁰ számot kell kipróbálni, ami nagyobb, mint a világegyetem bármilyen paramétere. Kis ravaszsággal észrevehetjük, hogy elegendő a szám négyzetgyökéig kipróbálni a számokat. De ez sem segít eleget: egy 100 jegyű szám négyzetgyöke 50 jegyű, és 10⁵⁰ is messze túl van a lehetőségek határán.

Kiderül, hogy az első kérdés sokkal könnyebb, mint a második: olyan hatékony (polinomiális) algoritmusok vannak, amelyek akár 1000 jegyű számról is könnyedén eldöntik, hogy prím-e. A tényezőkre bontásra azonban csak olyan algoritmus ismert, amely lényegében exponenciális: 100-nál több jegy esetén már csak nagy üggyel-bajjal működnek, 150 jegy fölött pedig egyáltalában nem. Látni fogjuk, hogy ennek az egyszerű ténynek hallatlan gyakorlati következményei vannak.

Hogyan lehetséges, hogy a prímfaktorizáció ennyivel nehezebb, mint a prímtesztelés? Azt gondolnánk, hogy mindegyikhez végig kell próbálni az adott számnál kisebb számokat, hogy nem osztható-e velük az adott szám. Nyilvánvaló, hogy ez nagyon hosszadalmas lenne, ezért valahogy másképp kell eljárnunk. A hatékony prímtesztelő algoritmusok az ún. „kis” Fermat-tételen alapulnak (a „kis” jelző nem a tétel fontosságára utal, hanem azért használjuk, hogy megkülönböztessük a csak nemrégen bebizonyított „nagy” Fermat-tételtől. Fermat, a 17. századi francia matematikus csak az előbbinek a bizonyítását adta meg.)

Fermat tétele szerint, ha p prímszám, és a tetszőleges egész szám, akkor

 p | a^p-a

(p osztója az a^p-a számnak). Például, 2⁵-2=30 osztható 5-tel. Ha egy p számról el akarjuk dönteni, hogy prímszám-e, akkor megnézzük, 2^p-2, 3^p-3 stb. oszthatók-e p-vel. Ellentétben a fenti egyszerű teszttel, ezt nem kell nagyon sok számra kipróbálni, elegendő csak néhányra.

(Sok mindent söpörtem itt a szőnyeg alá: néhány p számra ez a módszer hamis pozitív eredményt ad, ezért kicsit módosítani kell; nagy számok nagyon nagy hatványaival kell számolni, ami megoldható, de nem nyilvánvaló, hogyan stb. De mindezeket megoldva ez a teszt, melyet Miller-Rabin-tesztnek hívnak, mint láttuk, nagyon jól működik.)

III. A véletlen új fogalma(i)

A véletlen a modern tudomány egyik sarkalatos fogalma. Szinte minden tudomány lépten-nyomon használ olyan modelleket, melyekben a jelenségek véletlen, statisztikus jellege dominál.

Ugyanakkor a véletlen igen nehéz fogalom is. Véletlen-e az, hogy egy földobott pénz fejre vagy írásra esik? Ha jól meggondoljuk, miért is ne tudná egy igazán éles szemű és gyors eszű ember azalatt, amíg a pénz fölfelé száll, megfigyelni a pályáját, perdületét és amit csak még kell, és ebből kiszámítani, hogy melyik oldalára fog esni? A valóságban (talán a kvantumfizikát leszámítva) csupa olyan „véletlen” jelenséggel találkozunk, melyek igazából nem véletlenek, csak megjósolásukhoz nem áll rendelkezésre elegendő adat és idő.

1. Mitől nem véletlen egy sorozat?

Nézzük a véletlen legegyszerűbb matematikai modelljét. Dobjunk fel egy pénzdarabot mondjuk 100-szor, és írjuk le, hogy fejet vagy írást kapunk. Valami olyasmit fogunk látni, mint amit az alábbi ábra mutat.

Tényleg véletlen pénzdobálással kaptam ezt a sorozatot? (Nem árulom el.) Ezt a kérdést nem is könnyű eldönteni.

Persze ha valami könnyebbet kérdeznék, például a 4. ábrán látható sorozatot, akkor mindenki azonnal látná, hogy ez nem lehet véletlen. Tudjuk, hogy a pénzfeldobásnál ugyanannyi a fej, mint az írás valószínűsége, ezért egy hosszú pénzfeldobás-sorozatban körülbelül ugyanannyi fej kell legyen, mint írás.

Nézzünk akkor egy újabb sorozatot! (5. ábra) Ebben ugyanannyi fej van, mint írás, mégis nyilvánvaló, hogy ez se véletlen. (Mondjuk, érvelhetünk azzal, hogy a páros helyeken is fele-fele arányban kellene fejet és írást látni.)

Nézzük a következőt! (6. ábra) Ez már sokkal kevésbé szabályos, sokkal véletlenszerűbb, de azért gyanús. Aki jártas a valószínűségszámításban, rögtön látja, hogy túl gyakran váltakozik, nincsen benne például 3 egyforma betű egymás után. De a legmeggyőzőbb, ha elmondom: a sorozat k-ik eleme c, ha a k-1 szám kettes számrendszerbeli alakjában az 1-esek száma páratlan, és c, ha páros. Noha a sorozat meglehetősen szabálytalan, igen egyszerű szabállyal leírható, tehát egyáltalában nem véletlenszerű.

Nézzünk most egy számsorozatot is! (7. ábra) Véletlen-e ez? Gondolom, többen észrevették, hogy ezek egyszerűen a „pi” jegyei. 

Még egy sorozatot nézzünk meg! (8. ábra) Ez már igazán véletlenszerűnek tűnik! Még a valószínűségszámításban jártas olvasó is nehezen találna kivetnivalót benne. Pedig ez is „pi”, csak most 2-es számrendszerben van felírva.

2. Információtartalom és véletlenség

Az elsőnek megadott sorozatot (3. ábra) azonban nem tudnám ilyen egyszerűen leírni, definiálni: igazában semmi más értelmes módon nem írható le, mint azzal, hogy felsoroljuk az elemeit. Pontosan ezzel definiálhatjuk a véletlen sorozatot: egy sorozat akkor véletlen, ha nem írható le rövidebben, mint a saját hossza.

Általánosabban megfogalmazva azt nevezzük egy sorozat vagy bármilyen más struktúra, kép stb. informaciótartalmának (vagy másnéven információs bonyolultságának), hogy milyen hosszú a lehető legrövidebb leírása, mennyire lehet tömöríteni a sorozatot a lehető leghatékonyabb kódolást használva. (Ez matematikailag pontosan definiálható.)  Ezek után véletlen az a sorozat, melynek az információtartalma a hosszánál nem lényegesen kisebb. Megmutatható, hogy az ilyen módon definiált véletlen sorozatokra a valószínűségszámítás alapvető eredményei, például a nagy számok törvényei érvényesek lesznek.

A 19-20. század fordulóján Hilbert, a nagy német matematikus megfogalmazta az akkori matematika legfontosabb megoldatlan problémáit. Ezek egyike a valószínűség fogalmának megalapozása volt. Először von Mises tett kísérletet arra, hogy ezt megoldja, olyasformán, ahogyan mi próbáltuk az előbb: egy fej-írás-sorozatot véletlennek nevezett, ha a sorozatban közel azonos a fejek és írások gyakorisága, és ez áll akkor is, ha csak minden második vagy minden harmadik elemet nézzük stb. Ez azonban nem vezetett sikerre.

A 30-as években Kolmogorov (9. ábra) egészen más úton elindulva, az analízis eszközeit (a mértékelméletet) felhasználva alapozta meg a valószínűség fogalmát. Ez matematikailag nagyon jól használható volt, azonnal elterjedt, és mindenki úgy tekintette, hogy ezzel a probléma meg van oldva. Kivéve magát Kolmogorovot, aki a 60-as években visszanyúlt von Mises kísérletéhez, és azt úgy fejlesztette tovább, hogy matematikailag használható lett. Ezzel nagy lépést tett a véletlen nehéz fogalmának megértése felé. 

Egy sorozat információtartalmának a definíciója a valószínűség fogalmától függetlenül is sok izgalmas megoldatlan kérdéshez vezet: Mekkora a genetikus kód, például egy emberi kromoszóma információtartalma? Mekkora az agy bonyolultsága? Milyen nagyságrendű az egész világegyetem bonyolultsága?

3. Véletlen és álvéletlen

Van azonban a bonyolultság fogalmának egy hátránya is: egy sorozat bonyolultságát nem lehet semmilyen algoritmussal sem kiszámítani. Továbbá, ilyen értelemben véletlen számokat számítógéppel generálni fából vaskarika, hiszen egy számítógéppel generált sorozat információtartalma csak annyi, mint az őt generáló program információtartalma, ami a sorozat hosszától függetlenül korlátos.

Mivel azonban számítógép által generált véletlen számokra szükség van, egy másik fogalommal kell dolgozni. A bonyolultságelmélet segítségével két új kritériumot kaphatunk arra a kérdésre, mikor tekinthetünk egy sorozatot véletlennek.

1) Képzeljük el, hogy két gépünk van, melyek mindegyike 0-kat és 1-eseket nyomtat egy papírra. Az egyik gépben egy igazi véletlent előállító fizikai eszköz van, és a kiadott sorozat egymástól független bitekből áll, melyek 1 valószínűséggel lehetnek 0 vagy 1.

A másik gépben egy program gyártja a számokat egy rövid „magból”, azaz egy olyan számból, amely a generáló algoritmus kiinduló (inicializáló) értéke. A programot ismerjük, a magról azonban csak annyit tudunk, hogy hány jegyű. A legfontosabb: nem tudjuk, melyik gép melyik. A feladatunk, hogy ezt megtippeljük. (Előfordulhat, hogy a valódi véletlent adó gép véletlenül olyan sorozatot állít elő, melyet az álvéletlent adó gép is előállíthat. Ebben az esetben nem tudunk biztos választ adni. Ennek azonban igen kicsi a valószínűsége.)

Ha korlátlan idő állna rendelkezésre, akkor könnyű volna igen jó eséllyel tippelni: egyszerűen kipróbálnánk minden egyes magot, hogy abból indulva melyik generátor produkálja a megfigyelt sorozatot. Ehhez azonban 2ⁿ sorozatot kell kipróbálnunk. Így ezt a túl könnyű megoldást kizárhatjuk azzal, hogy csak hatékony (polinomiális) algoritmust engedünk meg.

Egy másik triviális, érdektelen megoldás az volna, ha úgy tippelnénk meg, melyik sorozat az igazi véletlen, hogy feldobunk egy forintot. Az esetek felében ez jó eredmenyt ad. Ahhoz, hogy ezt kizárjuk, megköveteljük, hogy a felismerő algoritmus az esetek több mint felében adjon jó eredményt. Pontosabban azt követeljük meg, hogy annak a valószínűsége, hogy az algoritmus helyesen tippeli meg, melyik sorozat a véletlen, legalább 51% legyen.

Akkor mondjuk tehát, hogy a generátor az igazitól megkülönböztethetetlen, ha nincs olyan algoritmus, mely polinomiális időben az esetek 51%-ában helyesen tippeli meg, hogy melyik gép az, amelyik a valódi véletlen sorozatot adja.

2) Képzeljük el, hogy csak egy gépünk van, melyről tudjuk, hogy álvéletlen-sorozatot állít elő, ismert programmal, de a magról ismét csak azt tudjuk, hogy milyen hosszú. Megfigyeljük a kijövő sorozatot, de mielőtt egy-egy újabb jegyét megnéznénk, megpróbáljuk megtippelni, hogy mi lesz a következő. Az előzőekhez hasonlóan, a tippeléshez csak polinomiális időt használhatunk, és annyit kell elérjünk, hogy az esetek 51%-ában sikeresen tippeljünk. Ha nincs ilyen algoritmus, akkor azt mondjuk, hogy a generátor megjósolhatatlan.

Ez a két definíció ekvivalens: ha egy álvéletlen sorozat az igazitól megkülönböztethetetlen, akkor megjósolhatatlan, és viszont. Ez egyáltalában nem nyilvánvaló.

Még kevésbé nyilvánvaló az, hogy létezik elméletileg is jó generátor - ez a kérdés azonban nem fér bele ebbe az előadásba. Annyit mégis meg szeretnék jegyezni: ez is azon alapszik, hogy míg két számot könnyű összeszorozni, nem könnyű egy számot tényezőire bontani.

Ezeknek az eredményeknek filozófiai tartalma is van. Van-e értelme valamit „kiszámíthatónak”, „determináltnak” nevezni, ha csak „elvileg” számítható ki, ami azt jelenti, hogy a számítás a világ végezetéig tartana?

Az előadás befejező része itt olvasható.