Тетрис - весьма популярная видеоигра, представляющая собой падающие кирпичики, изобретённая в1985 г. российским компьютерным инженером Алексеем Пажиновым. В 2002 г. спесиалисты по компъютерным вычеслениям количественно оценили трудность игры "Тетрис" и показали, что она имеет сходство со сложнейшими проблемами математики, которые не имеют простых решений, а для нахождения оптимальных решений требуют полного перебора вариантов.
В тетрисе игральные фигурки появляются в верхней части игрового поля и падают вниз. По мере медленного падения вниз данной фигурки, игрок может поварачивать её, либо двигать из стороны в сторону. Фигурки называются "тетрамино" и состоят из четырёх соедененных вместе квадратиков.
Тетрамино имеют форму буквы "Т", либо другую более простую форму. Когда одна фигурка достигает своего места в нижней части поля, где она останавливается, сверху начинает падать следующая. Всякий раз, когда ряд внизу заполняется квадратиками без пробелов, этот ряд удаляется, а все ряды выше него опускаются на один ряд вниз. Игра заканчивается, когда новая фигурка тетрамино не сможет упасть, потому что она блокируется. Цель игрока заключается в том, чтобы играть как можно дольше для максимального увеличения своего счёта.
В 2002 г. Эрик Д. Демэйн, Сьюзан Хохенбергер и Дэвид Либен-Новелл иследовали обобщенную версию этой игры, в которой сетка игрового поля могла бы иметь любое количество квадратов в ширину и высоту. Эта группа исследователей обнаружила, что, если попытаться максимально увеличить количиство рядов при игре с заданной последовательностью тетрамино, то игра окажется NP-полной ("NP"-расшифровывается как "недетерминировано-полиномиальная"). Несмотря на то что задачу такого класса можно проверить на предмет правильности ее решения, в действительности для нахождения ее решения может потребоватья чрезмерно много времени.
Классическим примером NP-полной задачи является задача коммивояжера, которая состоит в нахождении кратчайшего маршрута продавца, либо сотрудника службы доставки, который должен посетить много разных городов. Такие задачи являются трудными, потому что нет быстрого и эффективного алгоритма для поиска их решений.