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.