Kereső toggle

A matematika legnagyobb kihívása

Továbbítás emailben
Cikk nyomtatása

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. (Index)

Olvasson tovább: