Elõzõ rész

A matematikai kutatás hagyományos, 2500 éves paradigmája a következõ: az ember definiál egy fogalmat, kimond róla egy tételt, majd azt bebizonyítja. Talán kevésbé elismert, de nem kevésbé régi tevékenység algoritmusok tervezése. Hogy ennek igazán klasszikus voltát lássuk, idézzük fel, hogy Eukleidesz leír egy olyan algoritmust, mely két egész szám legnagyobb közös osztójának kiszámítására szolgál, és melyet ma is használunk, euklidészi algoritmus néven; vagy azt, hogy a numerikus matematika legfontosabb módszere egy egyenlet gyökeinek kiszámítására Newton módszere.

  A matematikai tevékenység e két, meglehetõsen különbözõ módja azonban nagyon sok szálon összekapcsolódik (l. melléklet, vagy részletesebben [6]). Az is nyilvánvaló, hogy a számítógépek nagymértékben növelték az algoritmustervezés fontosságát és presztízsét.

  A kutatói közösség növekedése miatt viszont a hagyományos paradigmák ki kell, hogy egészüljenek a tudományos teljesítmény új formáival. Ilyen lehet például a jó expozék és áttekintõ cikkek írása, problémák és sejtések megfogalmazása, példák összeállítása vagy kísérletek és az eredményeikrõl szóló beszámolók írása. E felsorolás elsõ két tagjáról itt bõvebben is szeretnék szólni.
 
 

Áttekintõ cikkek. A matematikai társadalom egységére leselkedõ legnagyobb veszély éppen a kutatói tevékenység kiterjedt volna. Senki sem tudja az újonnan megjelenõ cikkeknek akár csak a töredékét is végigolvasni.

  E problémára megoldás lehet egy olyan tevékenységi forma kialakítása, amely a kutatási eredmények másodlagos feldolgozását tûzi ki célul. Ezt a tevékenységet, jobb híján, ismertetõ írásnak nevezném, bár a magam részérõl nem annyira az írás, mint inkább a matematikai kutatás egy formájának tartom, ami például egy eredmény hatásának és más területeken elért eredményekkel való kapcsolatának felkutatásával foglalkozik, vagy egyes eredmények magyarázásával, lefordításával más szubkultúrák számára.

  A matematikusközösség már feltalálta ezt a tevékenységet: egyre nagyobb ugyanis az igény az írott ismertetõkre, áttekintésekre, minikurzusokra, kézikönyvekre és enciklopédiákra. Rengeteg konferencia létezik, ahol nagyrészt vagy teljes mértékben áttekintõ jellegû elõadásokat szerveznek, és a kiadók is jobban kedvelik az áttekintõ jellegû írásokból összeállított köteteket, mint az új kutatási eredményeket tartalmazó cikkekbõl állókat.

  Vannak aztán olyan intézmények és fórumok, melyek fokozatosan átalakulva egyre inkább az ismertetés szolgálatába állnak. A Nemzetközi Matematikai Kongresszust négyévente szervezzük meg, immár több, mint 100 éve. Sokan vannak a matematikusok között, akik a Kongresszust haszontalannak tartják (mint ahogy az is, ha kutatói konferenciának tekintjük), más tudományok kutatói viszont irigyelnek minket érte. Ha a matematikai tudomány egységének megõrzésére használjuk, akkor nagy érték: olyan fórum, mely egyedül képes arra, hogy a matematika egészének legfontosabb új eredményeirõl és az alkalmazások új területeirõl és módjairól áttekintést adjon.

  Ennek ellenére nem szívesen fogadjuk el az ismertetõ és áttekintõ írást tudományos tevékenységnek. Tartózkodóan fogadjuk, ha valaki összefoglalót ír másnak az új eredményérõl. Én a magam részérõl mégis úgy érzem, ezt a fajta tevékenységet éppen, hogy támogatni kell. Ha az ismertetõ írás elismert tudományos tevékenységgé lesz, értékelésére is új módokat kell találni. Hogyan illeszthetnénk bele a teljesítményrõl alkotott képünkbe, a munkahelyek, elõléptetések és kutatási pályázatok rendszerébe?

  Keveset tudunk a jó matematikai áttekintõ cikk kritériumairól. Nincsenek jól meghatározott formai követelmények pl. arra vonatkozóan sem, hogy egy elmélet mikor jó. Minden elmélet meglehetõsen pontos feltételeknek kell, hogy megfeleljen (új, nemtriviális és helyes kell legyen), de a matematikustársadalom egyéb, olyan követelményeket is támaszt (mint az, hogy érdekes és fontos legyen), amelyeket sokkal nehezebb formálisan meghatározni.

  Elfogadhatunk-e matematikai eredménynek egy áttekintõ írást? Néhány ritka esetben a válasz erre a kérdésre egyértelmûen igenlõ. Egy olyan áttekintést, ami két, látszólag nem is rokon területet elõször hoz összefüggésbe, vagy elõször mutat rá egy elmélet új alkalmazási lehetõségére, késõbb elméletekkel egy szinten említenek. De talán nem ez a jó áttekintõ írás legfontosabb kritériuma.

  Hadd vessek föl egy radikális ötletet: értékeljük az áttekintéseket úgy, ahogy a bölcsészek értékelik a munkájukat. A matematikusok hajlamosak a bölcsészetet “puha” tudománynak tekinteni, és a bölcsész sikerét (a mi “kemény és egzakt” tudományunkban elért sikerrel ellentétben) szerencse dolgának tartani, vagy, ami még rosszabb, az önreklámozási tehetség eredményének. Nyilvánvaló, hogy ez távol esik az igazságtól, és a bölcsészettudománynak megvannak a saját kritériumai a kiválóság és a siker elismerésére. Csak hasznunkra válhat, ha mi is megtanuljuk hasonlóképpen, a matematika “egzakt” kritériumai nélkül jutalmazni a kiváló teljesítményeket, az emberi gondolkodás hatalmas kincstárából más módszereket is beépítve a matematikai kutatásba.
 
 

Problémák és sejtések. Sejtésnek nevezzük a matematikában az olyan problémát, hipotézist, mely pontosan olyan jól meg van fogalmazva, mint egy tétel, “csak” a bizonyítása hiányzik. Persze egy jó sejtésnek kellõen súlyos “bizonyítéka” kell, hogy legyen: példák, speciális esetek, analógiák, nem matematikai precizitású (de azért nem is semmitmondó!) megfontolások, “heurisztikák” kell, hogy alátámasszák.

  Híres sejtések, mint pl. a Fermat-sejtés, nagy hajtóerõt jelentettek mindig is a kutatásban, a megoldásukat célzó kutatások igen sok olyan eredményhez vezettek el, melyek az eredeti sejtés témakörén messze túlmutattak. Amirõl itt beszélni szeretnék, az az, hogy a fent említett trendek, hogyan növelik a sejtések fontosságát.

  Egy kis közösségen belül mindenki nagyon hamar értesül az éppen aktuális problémákról. Ha viszont ez a közösség 100000 emberbõl áll, a problémákat nagyon pontosan kell meghatározni, hiszen a rosszul feltett kérdés unalmas és jelentéktelen eredmények sokaságához vezet. Ez azt jelenti, hogy a sejtések megfogalmazását az eredményekkel azonos szinten kell értékelnünk. A sejtést, mint olyat mûvészi szinten mûvelte a nemrég elhunyt Erdõs Pál, aki egymaga több sejtést fogalmazott meg, mint talán a világon valaha élt minden matematikus összesen. Erdõs a sejtéseit matematikai munkássága szerves részének tartotta, ugyanúgy, mint a tételeit. Egyik legkedvesebb emlékem Erdõstõl a következõ megjegyzés: “Soha senkit nem irigyeltem tétel miatt, de téged most irigyellek ezért a sejtésért.”

  Természetesen a sejtéseknél is hasonló nehézségekkel kell szembenéznünk, mint az áttekintéseknél, mert nagyon nehéz megmondani, mitõl jó egy sejtés. Erdõs kérdéseinek a stílusa is hatalmas viták kiindulópontja lett. Abban mindenki egyetért, hogy ha jó egy sejtés, akkor a megoldása komolyan elõrelendíti tudásunkat. Sok matematikus úgy érzi, ez a helyzet, ha tisztán látjuk egy sejtés helyét a matematika épületében. Vannak viszont olyan sejtések, melyek annyira hozzáférhetetlenek a jelenlegi módszerekkel, hogy a megoldásuk, úgy érezzük, muszáj, hogy valami alapvetõen újat hozzon, csak nem tudjuk, pontosan hol.

  A sejtések egy másik forrása a kísérleti matematika, amit a számítógépek tesznek lehetõvé. Ennek sok példája közül itt a legszisztematikusabbat szeretném megemlíteni: S. Fajtlowicz amerikai matematikus kifejlesztett egy GRAFFITI nevû programot, mely gráfelméleti sejtéseket generál [4]. Ez a program a gráfok különbözõ paraméreteit számítja ki, és egy “érdekes” gráfokból álló hatalmas könyvtárt végignézve, összefüggéseket állapít meg köztük. Ezek az összefüggések persze még nem tételek, nem biztos, hogy a könyvtárban nem szereplõ (végtelen sok) gráfra is igazak; de a sok példa alapján bízvást nevezhetjük õket sejtéseknek, melyeket aztán matematikai módszerekkel bizonyítani kell.

  A fõ ellenvetés Fajtlowicz programjával kapcsolatban az, hogy az általa felvetett összefüggéseknek matematikai motivációja nincs, még ha igazak is, nem érdekesek. Eleinte magam is kételkedve szemléltem a matematikai problémákat felvetni próbáló számítógépet, egészen addig, amíg egyik sejtése engem is megigézett. E sejtésrõl késõbb kiderült, hogy a kommunikációs bonyolultságelmélet egy kulcskérdéséhez kapcsolódik. (A teljesség kedvéért hozzá kell tennem, hogy ugyanezt a sejtést már Van Nuffelen is felvetette több évvel korábban, késõbb pedig Alon és Seymour bebizonyította, hogy nem igaz; egy gyengített változata azonban ma is nyitott.)

  Az igazi kihívás az, hogy hogyan lehet e kísérleteket megfelelõen elvégezni, hogyan lehet eredményeikrõl beszámolni és azokat a matematikai tudományba beépíteni. Már említettem, hogy a bölcsészettudománytól kéne megtanulni s az ismertetõ írás megfelelõ módjait. Ehhez hadd tegyem még hozzá, hogy az utóbbi kérdésre viszont a kísérleti tudományokban kell keresnünk a választ.

Írásom utolsó és szükségszerûen valamivel technikaibb részében azt szeretném megmutatni, mennyit veszíthetünk, ha a matematika különbözõ részei közötti szakadékokat hagyjuk elmélyülni, és mennyit nyerhetünk, ha megpróbálunk föléjük hidakat verni.
 
 

Végtelen és véges. A matematikai gondolkodás egyik csúcsteljesítménye a végtelenség és folytonosság fogalmának megragadása. A halmazelmélet és az analízis a matematika központi területei. A véges (diszkrét) matematika is kinõtt a fejtörõk világából, és mint láttuk, sok alkalmazási terület fõ eszköze lett. Mégis, a “folytonos” és a “diszkrét” matematikát sok strukturális, módszertani és kulturális szakadék választja el.

  Talán fölösleges azzal érvelnem, hogy a diszkrét és a folytonos matematika kiegészítik egymást, kölcsönösen hasznosítják egymás módszereit és eszközeit. A végtelent például a végessel tudjuk megközelíteni. Bonyolult folytonos struktúrák “diszkretizálása” mindig is alapmódszer volt – a Riemann-integráltól kezdve a sokaság háromszögelésén át (például a homológiaelméletben), a parciális differenciálegyenletek rácson való numerikus megoldásáig.

  Ennek ellenére úgy gondolom, hogy a diszkrét matematika módszereinek alkalmazása a folytonos matematikában egyáltalán nem érte el azt a szintet, amit elérhetne. Ennek egyik oka talán az, hogy a kombinatorika nem érte még el az analízis vagy az algebra mélységét és erejét. Egy másik ok azonban lehet kulturális: egy diszkrét matematikus inkább tanult a Galois-elméletrõl vagy a Borsuk–Ulam-tételrõl, mint egy “klasszikus” matematikus például a Ramsey-elméletrõl vagy a Maximális-Folyam-Minimális-Vágás-tételrõl (a fiatalok körében ez a helyzet megváltozóban van, öröm látni, ahogy a legkiválóbbak egyforma természetességgel nyúlnak mindkét polcra eszközért).

  Valamivel mélyebb gondolat, hogy a végtelen gyakran (vagy talán mindig?) a nagyon nagy véges közelítése. A folytonos struktúrák gyakran tisztábbak, szimmetrikusabbak és gazdagabbak, mint diszkrét társaik (egy síkbeli rácsnak például sokkal kevesebb szimmetriája van, mint az egész euklideszi síknak). A diszkrét struktúrák “beágyazása” a folytonos világba természetes és jól használható módszer a tanulmányozásukra.

  Ennek klasszikus példája a generátorfüggvények felhasználása (folytonos változóval) egy sorozat struktúrájának elemzésére. De más fontos példák is akadnak. A topológia például maga a folytonosság tudománya, annak megértésére született; mégis, az algebrai topológia módszereit is felhasználták már tisztán kombinatorikai állítás bizonyításához (lásd a [2] áttekintést).

  A hatvanas–hetvenes években a diszkrét optimalizáció egyik vezetõ témája a lineáris programozás módszereinek alkalmazása volt. A legfontosabb kombinatorikus optimalizációs problémák könnyen megfogalmazhatóak mint lineáris programozási problémák, azzal a mellékfeltétellel, hogy egészértékû megoldást keresünk. Ezeket könnyû is megoldani, ha az egész értékekre vonatkozó feltételt nem vesszük figyelembe; igazából arra megy ki a játék, hogy hogyan lehet ezeket a lineáris programokat úgy felírni, hogy az egészértékûségi feltétel figyelmen kívül hagyása indokolt legyen, ne változtassa meg az eredményt.
 
 

A máshonnan származó eszközök ereje. Hogy a matematika egységére irányuló igényemet alátámasszam, hadd említsem az algoritmuselmélet egy közelmúltbeli fejleményét. A kiinduló példa egy egyszerû, gráfelméletbõl vett algoritmikus probléma: legyen adott egy (véges) G gráf; osszuk be a ponthalmazát két osztályra oly módon, hogy az ezeket összekötõ élek száma a lehetõ legnagyobb legyen. Bár egyszerûnek tûnik, ez egy meglehetõsen fontos probléma.

  Ez a feladat persze “elvileg” könnyen megoldható: nézzük végig az összes lehetséges kettéosztást, és válasszuk ki a legjobbat. Sajnos ez az egyszerû megoldás igen sok idõt igényel: egy n pontú gráf pontjait 2n módon lehet két osztályba osztani, ami már olyan, viszonylag kis gráf esetén is, amikor n = 50, csillagászati szám. Így minden kettéosztást végignézni gyakorlatilag lehetetlen. Olyan algoritmust keresünk ezért, melynek az idõigénye ennél sokkal kisebb. A számításelméletben az olyan algoritmust szokás hatékonynak tekinteni, melynek az idõigénye növekvõ gráfméret esetén csak úgy növekszik, mint a pontszám egy hatványa (nem exponenciálisan, mint a fenti algoritmus esetén).

  Már majdnem 30 éve bebizonyították, hogy ez a probléma “NP-nehéz”. Ez a technikai kifejezés körülbelül azt jelenti, hogy nincs hatékony (polinomidejû) módszer az optimális kettéosztás megtalálására (legalábbis ha elfogadjuk a bonyolultságelmélet alapvetõ hipotézisét, amelyet röviden úgy neveznek, hogy P=\NP). Kevesebbel kell tehát beérnünk, mondjuk a közelítõen optimális felosztás megtalálásával.

  Nagyon könnyû olyan felosztást találni, ahol az éleknek legalább a fele a két osztály között megy; ezt elõször Erdõs Pál vette észre a hatvanas években, egy egészen más kérdéssel kapcsolatban. (Egyszerûen vegyük sorra a pontokat, és mindegyiket helyezzük jobbra vagy balra aszerint, hogy melyik ad több keresztbe menõ élt. Minden lépésnél az újonnan behozott éleknek legalább fele keresztbe megy.) Mivel egy felosztásnál a legjobb esetben se mehet több él keresztbe, mint az összes, így olyan közelítõ megoldást kapunk, amely az optimumnak legalább 50%-át eléri.

  Tudunk-e ennél jobb arányt elérni? Ez az egészen ártatlan kérdés a közelmúltig megválaszolatlan volt, amikor, szinte egyidejûleg, két fontos eredmény született: Goemans és Williamson olyan hatékony algoritmust adott meg, amelynek a hibája kisebb, mint 13%; Hastad viszont azt bizonyította be, hogy nincs olyan hatékony közelítõ algoritmus, amelynek eredménye minden esetben 6%-nál közelebb van az optimumhoz (pontosabban, NP-nehéz ilyen algoritmust találni).

  Az algoritmusok elmélete igen nehéz terület, és az, hogy a legjobb elképzelhetõ hatékony közelítõ algoritmus hibáját ilyen szûk határok közé sikerült szorítani, igen meglepõ. A mi szempontunkból most azonban az a fontosabb, hogy mindkét eredményt váratlan helyrõl érkezett eszközökkel érték el (és amelyek ennek ellenére egy sor hasonló problémánál is alkalmazhatók).

  A “negatív” eredmény mintájára egy sor más optimalizálási feladatról is bebizonyítható, hogy bizonyos korlátnál jobban még közelítõen sem oldhatóak meg hatékonyan. Az elsõ ilyen bizonyítást Feige, Goldwasser, Lovász, Safra és Szegedy adta, az ún. interaktív bizonyítási rendszerek egy alapvetõ eredményét (Babai, Fortnow és Lund) alkalmazva, ami a bonyolultságelmélet egy nagyon érdekes, de elsõ ránézésre meglehetõsen speciális területe. Késõbb kiderült, hogy ebben a bizonyításban a legfontosabb matematikai konstrukció egy algebrai módszerekkel nyert hibajavító kód, tehát távoli rokona pl. annak az eljárásnak, amelyet a CD-lemezeknél használnak!

  A “pozitív” eredmény, maga az algoritmus is egy sor korábbi eredményre épül, egymástól távol esõ szakterületeket kapcsolva össze. A kulcslépés itt a szemidefinit optimalizáció használata, ami a lineáris programozás egy, a szimmetrikus mátrixok elméletére építõ kiterjesztése. Ebben az esetben sem egy elszigetelt eredményrõl beszélünk, hiszen a szemidefinit optimalizációt (véletlen algoritmusokkal kombinálva) sikerrel alkalmazták más közelítõ algoritusok tervezésében is.
 
 

Valószínûségelmélet. Ezzel olyan témához érkeztünk, amely talán a leggyakrabban játszik összekötõ szerepet a matematika különbözõ szakterületei között. Robbanásszerûen nõ a valószínûségszámítási módszerek fontossága a kombinatorikában, a gráfelméletben és az algoritmusok elméletében. Az integrálás, szimuláció és véletlen algoritmusok ún. Monte-Carlo-módszerében való hagyományos alkalmazásukon kívül használják még õket leszámlálásra, pontos és közelítõ optimalizációra, prímtesztelésre, és még hosszan folytathatnám a sort.

  A nemalgoritmikus gráfelméletbe Erdõs Pál (lásd pl. [1]) vezetett be valószínûségszámítási módszert az ötvenes években. Ennek alapgondolata az, hogy sokszor egy bizonyos, speciális tulajdonságokkal rendelkezõ struktúrát (gráfot, számsorozatot stb.) nem tudunk megkonstruálni, de véletlenszerûen választva egy nagyobb osztályból, a kívánt tulajdonság nagy valószínûséggel teljesülni fog. Ez a fogás mostanra a gráfelmélet alapvetõ és jól mûködõ eszközévé vált. A valószínûségszámítás olyan tételek bizonyításába került bele, amelyeknek látszólag semmi közük nincs hozzá.

  A valószínûségszámítás szerepe természetesen nem korlátozódik a kombinatorikára és a gráfelméletre, hadd említsem például a szitamódszert a prímszámelméletben, vagy a turbulencia analízisét a hidrodinamikában [3].
 
 

Mélyebb egység. A valószínûségelmélet persze csak egyfajta illusztráció ahhoz, hogy a matematika egysége a más szakirányoktól származó eszközök használatánál jóval mélyebben gyökerezik. A legtöbb alapvetõ kérdés természete nem a priori diszkrét vagy folytonos – mind diszkrét, mind folytonos problémaként is lehet modellezni õket.

  Az utóbbi években mintavételi algoritmusokkal foglalkoztam, amelyek egy véletlen elemet generálnak egy nagy és gyakran bonyolult halmazból. A kérdés a bolyongás (Markov-láncok) keverési idejének becsléséhez vezet (hány lépést kell tenni, mielõtt a lánc alapvetõen stacionárius lesz?). Az alkalmazás szempontjából a Markov-láncokat végesnek természetes tekinteni – egy számítógép által végzett számítás szükségszerûen véges. Az elemzés során viszont a konkrét alkalmazástól függ, hogy az ember véges vagy általános, mérhetõ állapotteret akar használni. Az általános matematikai kérdés valójában a diszperzió: érdekelhet minket a hõ diszperziója egy bizonyosfajta anyagban, egy bolyongás során a valószínûség diszperziója vagy más hasonló kérdések. Mindig van egy “Laplace-operátor”, amely a diszperzió egy lépését leírja. A diszperzió sebességét a Laplace-operátor spektrális rése határozza meg, de ha a spektrális résrõl nincs információnk, akkor a diszperziós sebességet az állapottér izoperimetrikus egyenlõtlenségeinek segítségével is meg lehet becsülni. A izoperimetrikus egyenlõtlenségek felállítására a leggyakrabban többtermékes folyamot kell (explicite vagy implicite) szerkeszteni. (A bekezdésben kevertem a hõtan klasszikus nyelvét a gráfelméletével, természetesen szándékosan.)

  A matematika felosztásának nincs természetes módja, de súlyos kommunikációs problémák alakulhatnak ki, ha nem vesszük figyelembe, hogy az egység megõrzésének költsége van. Nemcsak a szervezésre kell idõt áldozni, hanem a kutatási tevékenység egy részét ismertetõ írásra és ezek elolvasására is kell fordítani, valamint a matematika népszerûsítésére és arra, hogy meghallgatunk olyan matematikai problémákat, amelyek az elmélet vagy az alkalmazás különbözõ területein merülnek föl.

IRODALOM

1. N. Alon and J. Spencer, The Probabilistic Method. With an Appendix by Paul Erdõs, Wiley, New York, 1992.

2. A. Björner, Topological methods, in: Handbook of Combinatorics (eds. R. L. Graham, L. Lovász, M. Grötschel), Elsevier, Amsterdam, 1995, 1819–1872.

3. A. J. Chorin, Vorticity and turbulence, Springer, New York, 1994.

4. S. Fajtlowicz, On conjectures of Graffiti, Discrete Math. 72 (1988), 113–118.

5. P. Halmos, Applied mathematics is bad mathematics, in: Mathematics Tomorrow (ed. Lynn Arthur Steen), Springer-Verlag, New York, 1981.

6. L. Lovász, Algorithmic mathematics: an old aspect with a new emphasis, in: Proc. 6th International Congress on Math. Education, Budapest, 1988, J. Bolyai Math. Soc., 1988, 67–78.