テトリスとぷよぷよの全消し可能性問題はNP完全
一般化ぷよぷよの NP 完全性（論文）
因みに、スーパーマリオブラザーズの盤面をクリアする(一般化された)問題はPSPACE完全と呼ばれる複雑性クラスに属していることが証明されています。
PSPACE完全とは、問題のサイズに対して多項式オーダのメモリを使用して解ける問題の中で最も難しい問題のクラスに属するということをいいます。NP完全問題もPSPACE問題に含まれるので、PSPACE完全問題はNP完全問題よりも難しいと考えられています（ただし現時点ではNP≠PSPACEが証明されていないので「より難しい」と言い切ることはできません）。
※参考・引用資料：
スーパーマリオブラザーズをクリアするのはNP問題よりも難しかった！
Classic Nintendo Games are (Computationally) Hard（論文）
Super Mario Bros. Is Harder/Easier than We Thought （論文）
「倉庫番パズル」IPSJ Magazine Vol.43 No.11 Nov. (2002) 1253-1258