6

2 倍の指数時間でしか解けないコンピュータ サイエンスの重要な問題はありますか? そして、それらが存在する場合、それらはどのクラスの問題に属しますか?

4

1 に答える 1

10

ウィキペディアから：

計算複雑性理論では、一部のアルゴリズムには 2 倍の指数時間がかかります。

  • プレスバーガー算術の各決定手順には、少なくとも 2 倍の指数時間が必要であることが証明されています。

  • 体上のグレブナー基底の計算。最悪の場合、Gröbner 基底には、変数の数が 2 倍になる多数の要素が含まれる場合があります。

  • 連想可換統一子の完全なセットを見つける

  • 満足する CTL+ (実際には 2-EXPTIME-complete)

  • 実閉体での量指定子の消去には、2 倍の指数関数的な時間がかかります (円筒代数分解を参照してください)。

  • 正規表現の補数の計算

于 2013-02-11T17:45:21.980 に答える