Aside from problems such as the halting problem, which aren't computable, are there any useful problems in computer science that can only be solved in time $O(2^{2^n})$, or in time $O((n!)!)$? I've heard of many difficult problems which require O(2^n) algorithms, but none that have required running times worse than that... are there any of that sort?

  • 1
    $\begingroup$ You should define "useful". The mere existence of such problems is not helpful, enumerating problems with higher than exponential worst case complexities is also not very good objective. Have you tried searching for them? Why do you need them? Oh, and computing a Gröbner basis over field is also double exponential. $\endgroup$ – Evil Oct 6 '16 at 4:31
  • $\begingroup$ @Evil But is it known you can't have a faster algorithm, or are these just the best upper bounds we have? $\endgroup$ – Juho Oct 6 '16 at 5:42
  • 1
    $\begingroup$ @Juho it is a bit more complicated, it is $2^{2^{cn}}$ this is lower bound for some $c > 0$ proved by Rabin and Fischer, and upper is $2^{2^{2^{pn}}}$ for some $p > 1$, paper here, but lower one is nondeterministic. Gröbner basis is EXPSPACE-complete (paper lost in some folder). $\endgroup$ – Evil Oct 6 '16 at 6:20
  • 2
    $\begingroup$ The satisfiability and validity problems for the temporal logic $CTL^*$ are complete for double exponential time. $\endgroup$ – Jan Johannsen Oct 6 '16 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.