LOVÁSZ LÁSZLÓ
Véletlen és álvéletlen
A véletlen a modern tudomány egyik sarkalatos fogalma. A kvantumfizika különböző interpretációi ellentmondanak egymásnak abban, hogy van-e igazi véletlen a kvantumvilágban. A statisztikus fizika az anyag hőmérsékletét, nyomását, fázisátmeneteit nagyszámú atom véletlenszerű kölcsönhatásaként írja le. A biológia, kémia, közgazdaságtan, szociológia, statisztika, és szinte minden más tudományág 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? A pénzfeldobás eredménye a véletlen esemény iskolapéldája, de ha jól meggondoljuk, miért is ne tudná egy igazán éles szemű és gyors eszű ember az alatt, 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? Hogyan lehet megkülönböztetni az “igazi” véletlen jelenségeket az olyan jelenségektől, melyeknek a kimenetelét csak azért nem tudjuk megjósolni, mert nem áll rendelkezésünkre elegendő adat, vagy elegendő idő ahhoz, hogy kiszámítsuk?
Bármennyire jó volna a véletlen egy tiszta, “abszolút” fogalmával dolgozni, a gyakorlatban (talán az elemirész-fizika bizonyos kérdéseit kivéve) csupa olyan “véletlen” jelenséggel dolgozunk, melyek igazából nem véletlenek. A statisztikus fizikus a szoba levegőjének atomjait, mint véletlenszerűen mozgó és ütköző részecskéket képzeli el, holott azok mozgását a mechanika törvényei teljesen meghatározzák. A közlekedési mérnök az úton közlekedő autókat speciális eloszlású sztochasztikus folyamatnak tekinti, holott ha ismerné az ország lakosainak aznapi terveit, vezetési szokásait, az út pontos állapotát, akkor ki tudná előre számítani, hogy ki és mikor fog arra autózni. Úgy tűnik tehát, hogy a véletlen fogalmát a tudományos kutatásokban csak nagy megalkuvások árán, bűnös tudattal használhatjuk.
A számítógépek megjelenése ezt a “bűnt” csak tetézte, illetve teljesen tiszta formára kristályosította. Igen sok számításban, például a fent említett tudományos modellek szimulációjában, arra van szükség, hogy véletlen számokat generáljunk. Sőt (eléggé meglepő módon) olyan számítások hatékonyságát is nagymértékben fokozni tudja véletlen számok használata, melyeknek sem az adatai, sem az eredménye nincs kapcsolatban véletlen jelenségekkel. Olyan elemi, ősi kérdések tartoznak ebbe a körbe, mint annak eldöntése, hogy egy szám prímszám-e, annak ellenőrzése, hogy egy algebrai azonosság igaz-e, vagy a térfogatszámítás. A kriptográfia (titkosírás) és az adatbiztonság sok más területe a véletlen számok további nagy felhasználója.
Honnan vegyük ezeket a véletlen számokat? Egy pénzdarab vagy dobókocka feldobálása lassú és nehézkes (és kérdéses, hogy az így generált véletlen számsorozat egyáltalában véletlen-e). Lehet olyan fizikai eszközt csinálni, ami (legalábbis a tudomány mai állása szerint) igazi “véletlen” számokat generál. Pl. egy zárt térben radioaktív atomokat helyezünk el, melyeket egy Geiger-Müller számlálóval figyelünk, és aszerint írunk le 0-t vagy 1-et, hogy a számláló kattanásakor óránk másodpercmutatója páros vagy páratlan számot mutat. Korábban sokat használtak véletlenszám táblázatokat (pl. kaszinók feljegyzéseit).
A fent említett számításokhoz azonban olyan nagy mennyiségű és gyorsan elérhető véletlen számra van szükség, hogy ezeket táblázatból kiolvasni vagy fizikai eszközzel előállítani lehetetlen. Ezért a véletlen számokat számítógéppel kell generálni. Mármost ez nyilván önellentmondás: a számítógép által kiadott újabb és újabb “véletlen” számok nemcsak “elvileg” számíthatók ki, hanem ki is számítja őket maga a gép! Ezt persze a számítógéptudósok is látták: a gépek által generált “véletlen” sorozatokat álvéletlen (pszeudo-random) sorozatoknak nevezték el. A fenti logikai ellentmondás dacára, ha az álvéletlen számokat gondosan használták, ezek kielégítő számítási eredményre vezettek.
A számítógéptudomány azonban nemcsak azt tette, hogy a véletlen-álvéletlen problémának ezt a legtisztább esetét felszínre hozta: igen jelentősen közelebb vitt a probléma megoldásához is. Először is a hatvanas években Kolmogorov, Martin-Löf és Chaitin a véletlenséget az információ-tartalommal hozta összefüggésbe: az összes számsorozatok közül a legnagyobb információ-tartalma egy véletlen sorozatnak van, mert ennek minden egyes újabb eleme a korábbiaktól független, és ezért teljesen új információt hordoz. Munkájuk nyomán lehetővé vált, hogy egy számsorozat véletlen voltát definiáljuk. Ez jelentős előrelépés volt, de több szempontból sem tekinthető a végső szónak. Nem magyarázza meg az álvéletlen-számokat, a gyakorlatban pedig nemigen használható, mert (ez bizonyítható) egy számsorozat információ-tartalmát algoritmussal kiszámítani nem lehet.
Az utóbbi évek talán leglátványosabb sikerei közé tartozik, hogy az álvéletlen számok generálása konyharecept-gyűjteményből komoly tudományos témává fejlődött. Az algoritmusok bonyolultságelméletét használva, Yao pontos megalapozását adta az álvéletlen számoknak. Ez arra a gondolatra épít, hogy nem kell azt kikötni, hogy a sorozat kezdeti elemeiből a következő elem egyáltalában ne legyen előre jelezhető: elegendő, hogy reális idő alatt ne legyen előre jelezhető. Itt a “reális idő” kifejezés pontatlannak és a számítástechnika fejlődésétől függőnek tűnik; de (mint látni fogjuk) a bonyolultságelmélet eszközeivel elegánsan és matematikailag egzaktul definiálható.
Yao munkája viharos fejlődést indított el; kiderült, hogy a korábban használt generátoroka Yao által megfogalmazott igen szigorú feltételeknek nem tesznek eleget, de végül Goldreich és Levin olyan álvéletlen-generátort konstruált, mely eleget tesz ezeknek a feltételeknek is.
Az alábbiakban először a véletlen sorozatok információelméleti definícióját adjuk meg, majd vázoljuk az álvéletlen sorozat Yao-féle definícióját, végül néhány példát mutatunk arra, hogy hogyan lehet véletlen számokat használva olyan problémákat megoldani, melyeknek a véletlenséghez semmi közük nincs.
Mi a véletlen sorozat?
Dobjunk fel egy pénzdarabot mondjuk 100-szor, és írjuk le, hogy fejet vagy írást kapunk. Valami ilyesmit fogunk látni:
I F I F I F F I F F F I F I I I F F I F I I F F I F F I F F F I I F F I F I F I F I F I F I F F F I F I F I F I I I F F I F I I I F I F I F F I I I F I I F I F F F I I I F I F I I F F I F I F F I I F I F F I I F I F I I I F F I I F F I I F F F F F F I I I F F I F F F F F F F I I I I I F F I F F F F I I F F
Tényleg véletlen pénzdobálással kaptam-e 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 következő sorozatot:
F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F
F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F Fakkor 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 kb. ugyanannyi fej kell, hogy legyen, mint írás. Nézzük akkor aF I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I
F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F I F Isorozatot. 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:
F I I F I F F I I F F I F I I F I F F I F I I F F I I F I F F I I F F I F I I F F I I F I F F I F I I F I F F I I F F I F I I F I F F I F I I F F I I F I F F I F I I F I F F I I F F I F I I F F I I F I F F I I F F I F I I F I F F I F I I F F I I F I F F I I F F I F I I F F I I F I F F I F I I F I F F I I F F I
Ez már sokkal kevésbé szabályos, sokkal véletlenszerűbb, de azért gyanús. A valószínűségszámításban jártas olvasó rögtön látja, hogy túl gyakran váltakozik, nincsen benne pl. 3 egyforma egymásután. De a legmeggyőzőbb, ha elmondom: a sorozat k-ik eleme I, ha a k-1 szám kettes számrendszerbeli alakjában az 1-esek száma páratlan, és F, ha páros. Noha a sorozat meglehetősen szabálytalan, igen egyszerű szabállyal leírható, tehát egyáltalában nem véletlenszerű.
Még egy sorozatot nézzünk meg:
F I F F I F I F I I I I I F I I F F F F I I F F I I F F I I F F F F F F F I I F F F I F F F F I I F F I I F I I F I I I I F I I I F I F F I I F I F F F F F I F F I I I F I I F F I F F I I F F I F F F I F I F I F I I F I F I F I F F F F F I F I I F F F F F I I I F F F I F I F F I F F F F I F F I I I I I F
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 ezt is egyszerűen le lehet írni: a ?2-t felírtam 2-es számrendszerben, és minden 1-est F-fel, minden 0-t I-vel helyettesítettem. (De meg lehet-e ezt a sorozatot egy véletlen sorozattól különböztetni, ha nem mondom meg, hogy hogyan kaptam? Erre a kérdésre még visszatérünk.)
Az elsőnek megadott sorozatot 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. Kolmogorov, Martin-Löv és Chaitin gondolata éppen az volt, hogy a sorozat véletlenségét ezzel definiálják: egy sorozat akkor véletlen, ha nem írható le rövidebben, mint a saját hossza. Általánosabban, egy sorozat (vagy bármilyen más struktúra, kép, informaciótartalma (vagy másnéven információs bonyolultsága) az, hogy milyen hosszú a lehető legrövidebb leírása. Ez a definíció többféle módon tehető pontossá, pl. a programozás nyelvén: milyen hosszú az a legrövidebb (mondjuk) Pascal nyelven írt program, mely a sorozatot kinyomtatja? (Tekinthetjük a kérdést adattömörítési problémának is: mennyire lehet tömöríteni a sorozatot, a lehető leghatékonyabb kódolást használva?)
Ezekután véletlen az a sorozat, melynek az információtartalma a hosszánál nem lényegesen kisebb. (A “nem lényegesen” kitételt könnyű pontosítani: mondjuk, ha a sorozat hossza n, akkor az információtartlama legyen legalább n- log n.) 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.
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 kérdéshez vezet: mekkora a genetikus kód, pl. egy emberi kromoszóma információtartalma? Mekkora az agy bonyolultsága? Milyen nagyságrendű az egész világegyetem bonyolultsága?
Van azonban ennek a fogalomnak egy hátránya: egy sorozat bonyolultságát nem lehet semmilyen algoritmussal sem kiszámítani!
Véletlen számok generálása
Véletlen számokat számítógéppel, vagyis lépésről-lépésre meghatározott, determinisztikus programmal generálni (mint azt a bevezetőben láttuk) fából vaskarika.
Mivel azonban véletlen számokra szükség van, véletlenszám-generáló algoritmusokat régóta használnak. Igen egyszerű például a következő módszer: válasszunk egy irracionális, de jól kezelhető számot, pl. a 21/2-t, és írjuk fel kettes számrendszerben mondjuk 100 tizedes jegyig:21/2=1,011010100000100111100110011001111111001110111100110010010000100010110010111110110001001101100110111
A kapott 0-1 sorozat általában igen véletlenszerűen fog kinézni. (Ha nem akarunk 2-es számrendszert használni, pl. mert kalkulátorunk nem tudja a kívánt számot 2-es számrendszerben kifejezni, akkor azt is megtehetjük, hogy 10-es számrendszerben számítjuk ki a 21/2-t 100 jegyre, majd a páros jegyeket (0, 2, 4, 6, 8) 0-val, a páratlanokat (1, 3, 5, 7, 9) 1-gyel helyettesítjük. Így is ránézésre teljesen véletlenszerű sorozatot kapunk.
Közbevetőleg: ha racionális számból indulunk ki, akkor a jegyek sorozata periodikus lesz, tehát feltűnően nem véletlenszerű. Például:
1/7=0,001 001 001 001 001 001 001 001 001 001 001 001 001 ...
1/11=0,0001011101 0001011101 0001011101 0001011101 0001011101 0001011101 0001011101 0001011101...
A 21/2 jegyeiben nemcsak periodikusságot, hanem más szabályosságot sem tudunk megfigyelni. Pedig a szabályosság ott van, csak nem feltűnő. A jegyek sorozatának bármelyik jegyét ki tudjuk számítani (bár a számítás nem könnyű). A fő probléma azonban ezzel a módszerrel az, hogy mindíg ugyanazt a “véletlen” sorozatot adja.
Megtehetnénk, hogy más egész szám négyzetgyökét (vagy köbgyökét,...) vesszük. Kiderül azonban, hogy a jegyek viszonylag rövid sorozatából már azt is vissza lehet számolni, hogy melyik szám hányadik gyökét tekintjük.
A 21/2 jegyei egy más szempontból sem adnak ideális álvéletlen-sorozatot. Az egyes jegyeket kiszámítani, ahogy egyre előbbre haladunk a sorban, egyre nehezebb lesz.
Gyakorlati szempontból az olyan generátorok a jók, melyeknél az újabb jegyek kiszámítása nagyjából ugyanannyi munkát igényel. Neumann János volt talán az első, aki ilyen generátort javasolt. Induljunk ki egy tetszőleges X0 pozitív egész számból, az ún. “magból” (legyen mondjuk 20 jegye a kettes számrendszerben). Ezt négyzetre emeljük, majd a kapott 39 vagy 40 jegyű számnak kivesszük a középső 20 jegyét. Így egy X1 számot kapunk. Ezzel megismételjük az eljárást. Az így kapott X0, X1,... számsorozatot magát tekinthetjük véletlennek, vagy (ha igazán igényesek vagyunk) kiválaszthatjuk mindegyikből mondjuk a 9 jegyet.
Sajnos erről az eljárásról is kiderült, hogy nem igazán jó: általában igen hamar periodikussá válik. (Az persze, hogy előbb-utóbb periodikus lesz, nyilvánvaló: csak véges sok 20 jegyű szám van (pontosan, ha 0-t is megengedünk első jegyként, 220), és amint egy Xi szám megismétlődik, a sorozat periódikus lesz. Az igazi kérdés az, hogy “előbb” vagy “utóbb” következik-e ez be; a fenti meggondolásból csak annyi következik, hogy legfeljebb 220 (azaz kb. egymillió) lépésen belül lesz ismétlődés; sajnos azonban ez a tapasztalat szerint már sokkal előbb (pár száz lépés után) bekövetkezik.
A gyakorlatban legtöbbet a lineáris kongruencia-generátorokat használják. Ezeknek egy X0 pozitív egész szám a “magja”, és három másik pozitív egész szám, A, B és C a “paramétere”. Az X1 számot úgy kapjuk, hogy az AX0 +B számot elosztjuk C-vel, és csak az osztási maradékot tartjuk meg. Hasonlóan, az AX1 +B szám C-vel vett osztási maradéka az X2, stb. Használhatjuk, az előbbiekhez hasonlóan, az X0, X1, X2,… sorozatot, mint álvéletlen sorozatot, vagy kivehetjük minden Xi számnak valamelyik jegyét.
Nagy irodalma van annak, hogy hogyan kell az A,B,C paramétereket úgy megválasztani, hogy a kapott sorozat minél véletlenszerűbb legyen. Nehéz azonban általánosat mondani, és az ismeretek nagy része tapasztalati tényeket rögzít. Sőt megmutatható, hogy az alább ismertetésre kerülő egzakt kritériumoknak a lineáris kongruencia-generátorok általában nem felelnek meg.
Knuth hires könyvében érdekes személyes példát ír le a véletlenszám-generálás buktatóira. Elhatározta, hogy megalkotja a “abszolút” véletlenszám-generátort. Bonyolult programot írt ehhez, amit a könyvben be is mutat. Nem volna célja, hogy én is leírjam; elég annyi hozzá, hogy a legbonyolultabb trükkökkel próbálta a sorozat egymásutáni elemei között az összefüggésnek még az irmagját is kiirtani (például a program végrehajtása egy ponton egy véletlen programsorra ugrott). Amikor azonban a programot elindította, a kiadott sorozat néhány lépés után ugyanazt a számot kezdte ismételgetni! Knuth azt a következtetést vonja le, hogy “véletlen számok nem generálhatók véletlenül választott módszerekkel”. Nem elég az, hogy nem látunk rá okot, miért volna a sorozatban szabályosság; arra kell okot (bizonyítékot) látnunk, hogy nincs benne.
Mi az álvéletlen számsorozat?
Nos, az utóbbi évek fejlődése lehetővé teszi, hogy ilyen bizonyítékkal szolgáljunk.
Ennek a fejlődésnek az alapja az, hogy maga a fogalom pontos megfogalmazást nyert, és ennek alapján az is kiderült, hogy egyrészt a hagyományos algoritmusok többsége nem állít elő igazán jó álvéletlen számokat, másrészt azonban van olyan álvéletlen számokat előállító eljárás, mely a legszigorúbb követelményeknek is megfelel. (Ebből nem következik, hogy sutba kell dobni azokat az egyszerű, könnyen programozható, a gyakorlatban is bevált eljárásokat, mint pl. a lineáris kongruenciák, melyeket korábban sikerrel használtak. A definíció, mint látni fogjuk, annyira szigorú, hogy egy-egy algoritmus kíválóan működhet a gyakorlatban akkor is, ha elméletileg nem tökéletes. A meglepő az, hogy van olyan eljárás, mely mindezeknek a szigorú feltételeknek eleget tesz!)
Egy véletlenszám-generátor nem tud a semmiből elindulni; a sorozatot egy rövid véletlen “magból” kiindulva generálja. (Ez a mag lehet pl. a gép órájának állása a program elindításakor, vagy hasonló adat, ami sokkal kevesebb jegyből áll, mint amennyit generálni akarunk). Legyen ez a mag egy n bináris jegyből (0-ból és 1-ből) álló X0 sorozat. A generátor ebből egy N jegyből álló G(X0) sorozatot számít ki (ami akkor érdekes, ha N sokkal nagyobb, mint n). Mikor lesz ez a generátor “jó”?
Erre a kérdésre Yao kétféle választ is javasol:
(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/2 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. 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 2n sorozatot kell kipróbálnunk. Így ezt a túl könnyű megoldást kizárhatjuk azzal, hogy korlátozzuk az időnket: csak olyan felismerő algoritmust engedünk meg, melynek lépésszáma n-nel csak úgy növekszik, mint n-nek egy hatványa (tehát mint n2, vagy n5, de nem 2n). Az ilyen algoritmust a számítógéptudományban polinomiálisnak nevezik; ez a “reális idejű” vagy “hatékony” algoritmus legáltalánosabban használt modellje.
Egy másik triviális, érdektelen megoldás: úgy tippeljük meg, hogy 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, hogy 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.
Yao egyik fő eredménye az, hogy ez a két definíció ekvivalens: ha egy generátor az igazitól megkülönböztethetetlen, akkor megjósolhatatlan, és viszont. Ez egyáltalában nem nyilvánvaló. Következik belőle például, hogy ha egy generátor megjósolható, akkor a kiadott jegyeket visszafelé olvasva is megjósolható – erre a szép tényre nem tudok egyszerű magyarázatot.
Egy elméletileg (is) jó generátor
A Goldreich–Levin–generátornak nem tudjuk minden csínját-bínját ismertetni, de a kiindulási pontja igen érdekes: az egyirányú függvény fogalmán alapszik, mely a kriptográfiában is kulcsszerepet játszik (akár szószerint is értve a kulcsot...). Tekintsünk egy olyan függvényt, mely minden n hosszúságú x 0-1 sorozathoz egy másik n hosszúságú f(x) 0-1 sorozatot rendel. Az egyszerűség kedvéért tegyük föl, hogy f kölcsönösen egyértelmű: különböző x sorozatok f(x) képei különbözőek. Erre az f függvényre azt mondjuk, hogy egyirányú függvény, ha x-ből az f(x) könnyen kiszámítható, de f(x)-ből az x nem.
Az, hogy x-ből az f(x) könnyen kiszámítható, technikailag úgy van definiálva, hogy “polinomiális időben”. Az, hogy f(x)-ből az x nem számítható ki könnyen, kényesebb fogalom: annak kell teljesülni, hogy minden olyan polinom idejű algoritmus, mely f(x)-ből megpróbálja az x sorozatot megtippelni, csak az összes sorozat elenyészően kis hányadán lesz mondjuk 1%-nál nagyobb valószínűséggel sikeres.
Megmutatjuk, hogy ha van egy f egyirányú függvényünk, akkor hogyan lehet belőle álvéletlen-generátort csinálni. A generátor magja két véletlen n hosszúságú 0-1 sorozat, x=x1x2...xn és y=y1y2...yn. A generált álvéletlen sorozat első bitjét úgy kapjuk, hogy az x és y sorozatokat egymás alá írjuk, és megszámoljuk, hogy hány helyen áll egymás fölött mindkettőben 1-es. Ha ez a szám páratlan, akkor 1-t írunk le; ha páros, akkor 0-t. (Például: legyen x=011010100, y=110101111. Ekkor x és y közös 1-esei a 2. és 7. helyen állnak, azaz összesen 2 helyen; ez a szám páros, tehát a generátor 0-t ad.)
Ezek után az x sorozatot az f(x) sorozattal helyettesítjük (y-t vátozatlanul hagyjuk), és ugyanezen a módon kiszámítjuk az álvéletlen sorozat 2, jegyét. Majd f(x) helyébe az f(f(x)) sorozatot írjuk, és megkapjuk az álvéletlen sorozat 3-dik jegyét stb. Ezt az eljárást nagyon sokszor (akár n100-szor) ismételhetjük. Mivel f polinomiális időben kiszámítható, az x, f(x), f(f(x)), f(f(f(x))),... sorozatok egymás után (viszonylag) könnyen kiszámíthatók.
Az, hogy ez a véletlenszám-generátor jó (megjósolhatalan), egyáltalában nem nyilvánvaló. Itt csak arra vállalkozhatom, hogy pár mondatban sejttessem, min is múlik ez. Tegyük föl, hogy a generátor következő jegye megjósolható volna. Ekkor, mint azt megjegyeztük, a jegyek fordított sorrendben tekintve is megjósolhatóak volnának; mondjuk, hogy az első jegyet az összes többiből meg tudnánk jósolni. De az első jegy utáni jegyek mind az f(x)-től függnek, míg az első jegy x-től. Azt az algoritmust, mely az első jegyet a későbbeikből megtippeli, fel lehetne használni arra, hogy x-et f(x)-ből kiszámítsuk, legalábbis nem elhanyagolható eséllyel. Ez azonban lehetetlen, mert f egyirányú függvény.
Marad persze a kérdés, hogy van-e egyáltalán egyirányú függvény. E ponton a számítógéptudósnak töredelmesen be kell vallania, hogy nem tudja a választ. Pontosabban, van sok olyan függvény, amiről azt hisszük, hogy egyirányú: ki tudjuk hatékonyan számolni, de senkinek sem sikerült olyan algoritmust találnia, mely az inverz függvényt tudná hatékonyan kiszámítani, akár csak az esetek kicsi, de nem elhanyagolható részében is. (Ilyen függvényt lehet alkotni például abból az észrevételből, hogy néhány, mondjuk 100 jegyű prímszámot összeszorozni könnyű, de aztán a kapott számot – ha a tényezőit elfelejtettük – újra prímszámok szorzatára bontani nehéz.) Az azonban, hogy eddig senki sem talált ilyen algoritmust, persze nem bizonyíték arra, hogy a jövőben sem talál ilyet senki, és csak remélhetjük, hogy előbb-utóbb valaki bebizonyítja egzakt matematikai eszközökkel, hogy olyan polinomiális algoritmus, mely egy n jegyű számot prímtényezőire bontana, nincs is.
A véletlen ereje
Azonosságok. Kezdjük egy középiskolás feladattal: fennáll-e a következő azonosság:
(x1-x2)(x2-x3)(x4-x5)(x5-x6)(x6-x4) + (x1-x5)(x5-x3)(x2-x4)(x4-x6)(x6-x2) = (x1-x4)(x4-x3)(x2-x5)(x5-x6)(x6-x2) + (x3-x6)(x6-x1)(x2-x4)(x4-x5)(x5-x2)?
Ez akár egy (kellemetlen) dolgozatpélda is lehetne. Tudjuk, hogy csak fel kell bontani a zárójeleket, és összevonni az azonos tagokat. Ha minden tag “kiesik”, akkor az azonosság fennáll (ez fennáll).
De ha ezt a módszert végigcsináljuk, akkor bizony eléggé kellemetlen, hosszadalmas számolásban lesz részünk: a kifejtésben összesen 128 tag lesz (mielőtt minden kiesne).
Ha 5 helyett, mondjuk, 50 tényezős szorzatok szerepelnének, akkor a tagok száma 4?250 lenne, ami már csillagászati szám.Van azonban egy egyszerű trükk, amivel próbálkozhatunk. Helyettesítsünk a változók helyébe számokat. Ekkor nem kell a szorzatokat kifejteni, hanem az azonosság két oldalát 10-10 kivonással, 8-8 szorzással és 1-1 összeadással ki tudjuk számítani. Így viszonylag könnyű kiszámítani, hogy mondjuk x1=6, x2=3, x3=0, x4=7, x5=-2, x6=1 a fenti egyenlet mindkét oldala 690.
Ha a helyettesítés különböző értéket ad a két oldalon, akkor biztosan tudjuk, hogy az azonosság nem áll fenn. De mi van, ha a helyettesítés után azt találjuk, hogy a két oldal egyenlő? Következtethetünk-e arra, hogy az azonosság fennáll? Más szóval, ha az azonosság nem áll fenn, kideríti-e ezt ez az ellenőrzés? Logikailag persze nem következik ez. Például ha a fenti azonosságból elhagyjuk az utolsó szorzatot (amikor is persze nem lesz már azonosság), és utána minden változó helyébe ugyanazt az értéket helyettesítjük, akkor mindkét oldal 0 lesz.
De megtehetjük, hogy a változók helyére olyan számokat helyettesítünk, melyeket véletlenszerűen választunk, mondjuk 1 és a polinom fokának 10-szerese között. Ekkor nem nehéz bebizonyítani, hogy legfeljebb 1/10 annak a valószínűsége, hogy “beletalálunk” egy olyan speciális értékbe, amely mellett a két oldal egyenlő. (Ha ezt túl nagy kockázatnak érezzük, ismételjük meg e tesztet 10-szer. Ha egyszer is azt találjuk, hogy a két oldal nem egyenlő, tudjuk, hogy nem azonossággal van dolgunk. Ha mindannyiszor egyenlőséget kapunk, bátran kijelenthetjük, hogy az egyenlőség azonosság; legfeljebb 1 a tízmilliárdhoz az esélye, hogy tévedünk.)
Ami meglepő, az az, hogy nem tudjuk: lehet-e hatékonyan ellenőrizni egy azonosságot véletlen számok használata nélkül? Valószínű, hogy a válasz nemleges, de ezt nem tudjuk bebizonyítani.
Térfogatszámítás
Van olyan klasszikus probléma is, amelyről tudjuk (matematikai eszközökkel bizonyított tétel mondja ki), hogy véletlenszámok használata nélkül nem oldható meg hatékonyan, de véletlent használva igen: ilyen a térfogatszámítás. Sajnos itt az eredmény megfogalmazásához több matematikai eszközre van szükség, mint eddig, a térfogatot ugyanis magasabb dimenzióban (n dimenziós térben) akarjuk számítani. A testről, aminek a térfogatát ki akarjuk számítani, azt tesszük fel, hogy konvex (azaz bármely két pontját összekötő szakasz a testben halad).
Megtehetjük, hogy a testet, legalábbis közelítőleg, szimplexekre (n-dimenziós “tetraéderekre”) bontjuk, ezeknek a térfogatát külön-külön alkalmas formulával kiszámítjuk, és az így kapott térfogatokat összeadjuk. A baj az, hogy a szükséges szimplexek száma a dimenzióval exponenciálisan nő, így magas dimenzióban ez az eljárás nagyon nem hatékony.
Ez nem véletlen. Mintegy 15 évvel ezelőtt Elekes György, Bárány Imre és Füredi Zoltán bebizonyították, hogy bármely olyan algoritmus, mely a térfogatnak egy közelítését számítja ki, és az időigénye a dimenziószámmal csak mérsékelten nő (azaz csak úgy, mint n egy hatványa, vagyis mint n2, vagy akár mint n100, de nem úgy, mint 2n), szükségképpen nagyot téved valamely konvex testen: lesz olyan test, melynek a térfogatára adott becslése legalább egy nn nagyságú faktorral tér el az igazságtól.
Ezekután magas dimenziószám mellett a konvex testek térfogatszámítását úgy tekintette a közvélemény, hogy az reménytelenül nehéz.
Nagy meglepetést okozott ezért 1989-ben, amikor Dyer, Frieze és Kannan olyan algoritmust találtak, mely véletlen számok felhasználásával (az ún. Monte-Carlo módszerrel) minden n-dimenziós konvex test térfogatát tetszőlegesen kicsit hibával elvileg hatékonyan ki tudta számolni. Sajnos hozzá kell tenni, hogy “elvileg”, mert az algoritmus lépésszáma az n dimenziószámmal úgy nő, mint n27: ez polinomiális, tehát definíció szerint hatékony, de a gyakorlatban már 2-3 dimenzióban is reménytelenül lassú.
De az elméleti áttörés gyors fejlődést indított el: egyre-másra javították az algoritmust, csökkentették a 27-es kitevőt. A jelenlegi “rekordot” Kannan, Simonovits Miklós és a szerző tartják n5 nagyságrendű lépésszámmal (ez a gyakorlati alkalmazhatóság határán van), és talán további javítás is elképzelhető.
Az algoritmus a modern matematika több fejezetének eredményeire támaszkodik, és ismertetése túlnyúlna e cikk keretein. Kiindulási pontja a már klasszikusnak számító Monte-Carlo módszer. Eszerint a konvex testet (jelöljük K-val) befoglaljuk egy G gömbbe. A gömb térfogatát ki tudjuk számítani elemi analízisbeli módszerekkel. Generáljunk G-ben k egymástól független, egyenletes eloszlású véletlen pontot (ezt nem nehéz megtenni), és számoljuk meg, hogy ezek közül hány találja el K-t; legyen ez a szám t. Ekkor, ha k elég nagy, a t/k hányados jó közelítéssel megadja a K es G térfogatának az arányát, amiből a K térfogata már könnyen kiszámítható.
Sajnos az ördög a “k elég nagy” kifejezésben van elrejtve: a Monte-Carlo módszernek ebben az egyszerű változatában k-nak az n dimenziószámmal exponenciálisan kell nőnie. Az a baj ugyanis, hogy a K-t tartalmazó legkisebb gömb térfogata a K térfogatának akár 2n-szerese is lehet. Emiatt az első 2n pont, amit a gömbben generálunk, várhatóan el sem találja K-t, és így annak térfogatáról semmi információt nem szolgáltat.
Dyer, Frieze és Kannan kialakított egy olyan többfokozatú Monte-Carlo módszert, mely ezt a nehézséget megkerüli. A baj az, hogy ehhez nemcsak gömbben, hanem bonyolultabb konvex testekben is véletlen pontokat kell generálni; ez a módszer fő nehézsége. Ennek megoldásáról itt csak annyit tudunk elmondani, hogy a Markov-láncok módszerét használja.
Természet Világa, 2000. II. különszám
http://www.termvil.hu/archiv
Vissza a tartalomjegyzékhez