Are there any problems which requires more than double exponential time?

Question

Are there any problems, for which all known algorithms require more than double exponential time?

Answer 1

The time hierarchy theorem ensures that problems of this sort exist. As a very contrived example that's used by the theorem, consider the following problem:

Given a Turing machine M and a string x, does M accept x within 2²²ⁿ steps?

This problem provably cannot be solved by a TM in under 2²²ⁿ steps, and since a TM can simulate a computer with only an n⁶ slowdown, this means that no computer can solve this problem in time o(2²²ⁿ).

Granted, this isn't really an interesting problem (I can't see why you'd want to solve this except in very contrived situations), but it's known that this problem requires triple exponential time to solve.

Hope this helps!