雙指數問題？

Question

計算機科學中是否有任何重大問題只能在double exponential時間內解決？如果它們存在，那麼它們屬於哪類問題？

Answer 1

從Wikipedia：

在計算複雜性理論，一些算法取雙指數時間：

• 爲Presburger算術每一個決策程序可證明至少需要雙指數時間

• 在一個領域計算Gröbner基礎。在最糟糕的情況下，Gröbner基礎可能有多個變量數量是雙倍指數的元素。

• 找到了一套完整的關聯，交換unifiers的

• 通過滿足CTL +（這是，事實上，2-exptime完成）

• 量詞消除上實閉域需要雙重指數時間（參見圓柱代數分解）。

• 計算正則表達式的補