倍数指数問題？

Question

double exponential時間にしか解決できないコンピュータサイエンスに重大な問題はありますか？そして、それが存在すれば、どのクラスの問題に属するのでしょうか？ Wikipediaから

Answer 1

：計算複雑性理論で

、いくつかのアルゴリズムが二重指数時間がかかる：

• プレスバーガー算術のための各決定手順は、証明可能

• 少なくとも二重指数時間を要しますフィールド上のグレブナー基底を計算する。最悪の場合、グレブナー基底は、変数の数が2倍に指数関数的である多数の要素を持つことがあります。

• が本当閉じフィールド上

• 記号消去が二重指数を取る（、実際には、2-EXPTIME完全である）CTL +を満たす連想可換ユニファイアの完全なセットを見つけます時間（円柱代数分解を参照）。

• 正規表現の補数を計算