Double exponential problems? [closed]

Question

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.

Closed 9 years ago.

Are there any significant problems in computer science that can only be solved in double exponential time ? And if they exist then to which class of problems do they belong ?

Answer 1

From Wikipedia:

In computational complexity theory, some algorithms take double-exponential time:

• Each decision procedure for Presburger arithmetic provably requires at least double-exponential time

• Computing a Gröbner basis over a field. In the worst case, a Gröbner basis may have a number of elements which is doubly exponential in the number of variables.

• Finding a complete set of associative-commutative unifiers

• Satisfying CTL+ (which is, in fact, 2-EXPTIME-complete)

• Quantifier elimination on real closed fields takes a doubly-exponential time (see Cylindrical algebraic decomposition).

• Calculating the complement of a regular expression