EXPTIME
他のEXPTIME完全問題としては、一般化されたチェス、チェッカー、囲碁(日本ルール)での形勢を判断する問題がある(一般化されたゲームとは、盤のサイズと駒数をパラメータ化したもの)。これらのゲームは盤の大きさに対して指数回数の手数で終わることからEXPTIME完全となる。囲碁の場合、日本ルールは扱いにくいためEXPTIME完全となるが、アメリカルールや中国ルールはそれよりも扱いやすいため、EXPTIME完全となるかどうかは不明である。
一方、一般化されたゲームでも、盤の大きさに対して多項式回数の手数で終わるゲームはPSPACE完全であることが多い。指数回数の手数がかかっても、自動的に非反復となるゲームは同様である。
その他の重要なEXPTIME完全問題として、succinct circuit(簡潔回路)に関する問題がある。succinct circuit とは、指数関数的に少ない空間でグラフ問題を解くのに使われる単純な機械である。入力ノード数と出力ノード数を入力とし、それらの間にエッジを張る。隣接行列のような普通のグラフ表現で同じ問題を解こうとする場合は P完全となるが、succinct circuit では入力に要するビット数が指数関数的に少ないため、時間はEXPTIME完全となるのである。