Előd
7 °C
17 °C

Néha úgy érzed, mintha két valóság létezne?

Több infó

Támogasd a független újságírást, támogasd az Indexet!

Nincs másik olyan, nagy elérésű online közéleti médiatermék, mint az Index, amely független, kiegyensúlyozott hírszolgáltatásra és a valóság minél sokoldalúbb bemutatására törekszik. Ha azt szeretnéd, hogy még sokáig veled legyünk, akkor támogass minket!

Milyen rendszerességgel szeretnél támogatni minket?

Mekkora összeget tudsz erre szánni?

Mekkora összeget tudsz erre szánni?

A matematikusok szerint nehéz a tetris

2002.10.28. 13:48
Az MIT kutatói bebizonyították, hogy a tetris bonyolult játék, matematikailag ugyanis az igen nehezen megoldható NP-teljes problémák közé sorolható. Ezentúl tehát a munka helyett tetrisezők azzal a megnyugtató tudattal játszhatnak, hogy nemhogy nem lazsálnak, hanem az elméleti matematika egyik legnagyobb kihívásával küzdenek éppen.
Tizenhét évvel azután, hogy az orosz Alekszej Pajtinov megalkotta a tetrist, a Massachusetts Institute of Technology (MIT) kutatói végre bebizonyították, hogy a játék nehéz. A tetris azután vált igen népszerűvé, hogy a Nintendo is megjelentette, azóta is ez a legnagyobb példányszámban eladott játék a világon.

Erik Demaine és kutatótársai szerint a tetris a legbonyolultabb matematikai problémák csoportjába, az NP-teljes problémák közé tartozik, írta a Nature magazin. Ezek közül talán a legismertebb az utazó ügynök probléma, melyben az ügynöknek n számú városba kell eljutnia, mindegyikbe pontosan egyszer, a lehető legkisebb költséggel, azaz a legrövidebb útvonalon.

Demaine szerint emiatt szinte lehetetlen olyan algoritmust írni, ami képes gyorsan és hatékonyan játszani a játékot.

Hogy világos legyen

A matematikai problémák egy csoportját P-vel jelölik, mivel ezek megoldására létezik polinomiális algoritmus. Ezek megoldása egy adott számítási módszerrel mindig ugyanannyi időt vesz igénybe - egy adatbázisban például tízszer annyi tétel szortírozása tízszer annyi időbe kerül. Felteszik, hogy léteznek non-P problémák is, ezeknek nincs adott időn belül biztos megoldása. A non-P probléma létezésének bizonyításához az összes lehetséges számítási módszerről be kellene látni, hogy nem polinomiális. Ez eddig senkinek sem sikerült.

A non-P gyanúsított problémák egy csoportját NP-nek (nondeterminisztikus P) nevezzük. Az NP olyan probléma, amelynél meg lehet állapítani, hogy megoldása P. Ezen belül van még egy kisebb csoport, amelyet NP-teljes problémáknak neveznek - ezek olyanok, amelyekhez egyetlen polinomiális megoldás kulcs lenne minden NP-hez. Amennyiben tehát egy NP-teljes problémának P megoldása akad, minden NP P-nek bizonyulna. A sejtés az, hogy az NP problémákra nem létezik polinomiális megoldó algoritmus.

Ilyen nagy dolog tehát a tetris.

Addiktív

Az a tény tehát, hogy a tetris NP-teljes probléma, azt jelenti, hogy az egyes elemek legmegfelelőbb helyének megtalálására - akár időkorlátozás nélkül is - az egyetlen módszer minden egyes lehetőség végigpróbálgatása. Demaine szerint a tetrisre éppen a hatalmas intellektuális kihívás miatt lehet olyan könnyen rászokni.

A kétszemélyes játékok azonban még komplikáltabbak: a sakk például EXPTIME-teljes, azaz exponenciális időbonyolultságú probléma: a megoldáshoz szükséges idő exponenciálisan növekszik a tábla méretének növelésekor. A japán go az ilyen típusú játékok közül talán a legösszetettebb.