Lovász László

II. A bonyolultság új fogalma

A bonyolultság fogalma hasonló fejlődésen ment át az utóbbi 50 évben, mint sok más alapvető fogalom. Először egy megértést akadályozó körülményt jelentett (vagy talán csak kényelmes kifogást?). Ha egy jelenség vagy struktúra túl bonyolult, akkor a kutatás során megkerüljük, leegyszerűsítjük vagy részeire bontjuk. A következő fázist az jelenti a fogalom történetében, amikor a tudós elkezdi a bonyolultságot mint önálló jelenséget szemlélni: kidolgozza, hogy hogyan lehet mérni, szabályokat és törvényeket állapít meg, kapcsolatba hozza más, korábban megismert dolgokkal. Végül jelentkezik a mérnök, hogy a bonyolultságot eszközként használja fontos tervezési problémák megoldására: az adatvédelem, az elektronikus posta, a kereskedelem, a pénzforgalom biztonsága ma nagyrészt a bonyolultság fogalmán és annak tulajdonságain alapul.

A 19. századi matematika egyik nagy sikere a végtelen fogalmának megragadása volt. Ennek bűvölete olyan erős, hogy hajlamosak vagyunk mindenre, ami véges, rálegyinteni: "Véges sok eset van, amit végig lehet nézni!". A számítógépek megjelenése azt eredményezte, hogy rájöttünk: a véges nagyon nagy lehet, bekövetkezhet az "exponenciális robbanás".

1. Exponenciális robbanás

A sakkjáték feltalálójáról szóló klasszikus történet szerint az unalma elűzéséért hálás király felajánlotta neki, hogy azt kívánhat jutalmul, amit akar. A feltaláló azt kérte, hogy a sakktábla első mezejére tegyenek egy búzaszemet, a másodikra kettőt, a harmadikra négyet, a negyedikre nyolcat, és így tovább, minden mezőre kétszer annyit, mint az előzőre. A király nagyon megörült, hogy ilyen olcsón megúszta, de aztán rá kellett jönnie, hogy nemcsak, hogy a 10-12-ik mezőtől már nem férnek el a búzaszemek, de a tábla közepe táján már birodalmának teljes búzatermése sem lett volna elegendő, hogy ígéretét betartsa.

Ezt a jelenséget, hogy ha egy mennyiséget ismételten duplázunk (vagy bármilyen egynél nagyobb számmal szorzunk), akkor igen gyorsan növekszik, exponenciális robbanásnak hívjuk. Moore említett törvényében az a meglepő hogy az informatikában bekövetkezett exponenciális robbanás ilyen sokáig tud tartani. Az 1960-as évek környezetvédelmi forradalma mögött az áll, hogy egyre többen értették meg, hogy az exponenciális növekedés nem tarthat örökké, sem a népesség, sem a termelés, sem a fogyasztás területén.

A számítástudományban az exponenciális robbanás leggyakrabban akkor lép fel, ha azt a kijelentést, hogy "Véges sok eset van, amit végig lehet nézni!", megpróbáljuk közelebbről vizsgálni. Mondjuk, az esetek megkülönböztetéséhez először is két alapesetet kell megkülönböztetni; aztán ezek mindegyikén belül két újabb eset van stb. Ezt a logikai helyzetet a 2. ábrán látható hálózattal, ún. bináris fával ábrázolhatjuk.

2. ábra

Ezért aztán a számítástudományban elég hamar megfogalmazódott, hogy olyan algoritmusok tervezésére kell törekedni, melyek lépésszáma a feladat méretével csak mérsékelten nő, úgy, mint a méret egy hatványa, nem pedig exponenciálisan. Tehát ha a feladat mérete n, akkor a lépésszám lehet n² vagy n³, de nem lehet 2ⁿ. Az ilyen algoritmust polinomiálisnak szokás nevezni. A kétfajta növekedés közötti különbséget úgy lehet a legjobban szemléltetni, ha elgondoljuk, hogy mekkora teljesítménynövekedést lehet várni a technológia fejlődésétől. Tegyük fel, hogy mind az A algoritmus, mind a B algoritmus ma 50 bemenő adattal tud egy adott problémát megoldani. Az A algoritmus lépésszáma úgy nő a bemenő adatok számával, mint n³, a B algoritmusé, mint 2ⁿ. Ha várunk 10 évet, és a számítógép teljesítménye 32-szer akkora lesz, mint ma (Moore törvénye szerint), akkor az A algoritmus már 150 bemenő adattal bír el, míg a B algoritmus teljesítőképessége csak 55 adatra emelkedik.