2024. augusztus 3. – 13:29
Filantróp milliárdos, vérbeli üzletember, géniusz programozó, aknakereső-függő, profi székátugró, a konteós univerzum Antikrisztusa és palacsintarendező nagymester. Igen, Bill Gatesről van szó, és mielőtt valaki megkérdezné, hogy honnan jött a palacsinta a képbe, le is lőjük a poént: úgy, hogy Gates 1979-ben szerzőtársával közösen olyan hatékony megoldást publikált a palacsinták méret szerint sorba rendezésének összetett problémájára, hogy
harminc évre és jóval fejlettebb, jelentős részben neki köszönhetően létező számítógépekre volt szükség a felülmúlásához.
A palacsintarendezést 1975-ben vetette fel először egy amerikai professzor, és a problémát egyáltalán nem bonyolult elmagyarázni: képzeljük el, hogy egy étteremben dolgozunk, ahol a konyhán készülő, különböző méretű palacsintákat egy fordítólapáttal méret szerint sorba rendezzük. A lapátot bárhova bedughatjuk a palacsintatoronyba, hogy megfordítsuk az összes fölötte lévő palacsintát. A cél, hogy minél kevesebb fordításból megoldjuk a rendezést, hogy a palacsinták minél előbb a vendég elé kerüljenek, mielőtt mérgében faképnél hagyna bennünket.
Egyszerűnek tűnik? Alapvetően az is, hiszen akármennyi palacsintáról van szó, mindig működőképes megoldás lesz, hogy bedugjuk a lapátot a legnagyobb palacsinta alá, megfordítjuk a torony ezen részét, aztán benyúlunk legalulra, és megfordítjuk az egész tornyot, aztán ezt ismételgetjük, amíg nem végzünk. Ez a megoldás garantáltan eredményes, de nem túl hatékony, mert mindig kétszer annyi fordítást igényel, mint a palacsinták száma. Hatékonyabb megoldás azonban nem létezett,
egészen addig, amíg a Harvardon tanító matematikus professzor, Harry Lewis a hetvenes évek végén ki nem adta a feladatot az egyik óráján, ahol történetesen Bill Gates is ott ült diákként.
Az ekkoriban a húszas évei elején járó Gates pár napra rá megjelent Lewis irodájában, és közölte, hogy talált egy olyan megoldást, ahol kevesebb – a palacsinták száma szorozva 2 helyett mindössze 1,67 – fordításra van szükség a sorba rendezéshez. Lewis 2008-ban az amerikai National Public Radióban azt mondta, Gates kifejezetten okos megoldást dolgozott ki, és végül 1978 elején egy adjunktussal közösen ki is adott egy részletes tanulmányt, amelyben pontosan leírta az algoritmusukat.
Az ide kattintva elérhető tanulmányban négy elméletet mutatnak be, és további érdekességként megemlíthető, hogy tőlük függetlenül két magyar matematikus, Győri Ervin és Turán György is kidolgozták az általuk megalkotott algoritmust, és annak bizonyítását is. A Studia Scientiarum Mathematicarum Hungarica 1978-as számának 133. oldalától olvasható is a két magyar matematikus tanulmánya ugyanerről, a végén egy hasonló jelzéssel Gatesről és szerzőtársáról.
Az tehát biztos, hogy a hetvenes évek végén két helyen is dolgoztak a probléma megoldásán, a tanulmányok megjelenése után viszont harminc évig nem történt újabb előrelépés. Gates időközben otthagyta a Harvardot, hogy megalapítsa a Microsoftot, a többi pedig, mint azt mondani szokás, már történelem. A következő évtizedekben Gates tevékenyen hozzájárult a számítástechnika rohamos fejlődéséhez, és harminc évvel később épp az erősebb számítógépeknek köszönhetően befutott egy még jobb algoritmus, ami alig két százalékkal ugyan, de még hatékonyabbá tette a palacsintarendezést.
Azt, hogy a palacsintarendezés NP-nehéz, végül 2011-ben sikerült bizonyítani, ezzel egy évtizedek óta nyitott kérdést sikerült megválaszolnia a tanulmányt publikáló matematikusoknak. Ez azért is fontos, mert ily módon a dolog a matematika hét legkeményebb problémájának egyikével, a P versus NP problémával függ össze. Ez sokak szerint az egyik legfontosabb matematikai probléma, melynek megoldása számos területen járna messzemenő következményekkel, az NP-nehéz problémák pedig azért hasznosak, mert minden NP-probléma redukálható rájuk.
