# Are there superexponential NP-complete problems?

Are there any NP-complete problems where the fastest known algorithm solves the problem in superexponential time (like $$O(n!)$$ time)? Every NP-complete problem that I am aware of has fastest known algorithms that are all exponential time, but it is not obvious to me whether there is anything preventing such problems from having best-case algorithms that run in superexponential time.

• "Does nondeterministic Turing machine $M$ accept the empty input within time $|M|^{100}$" might qualify. Commented Aug 1, 2022 at 4:40

I’m not sure how you define “superexponential”, could you make it precise for me?

If you define "super-exponential" as something described in the previous link like $$2^{n^c}$$: In this context, $$O(n!)$$ (as you described) is something bounded by $$O(n^n) = O(2^{n\log n}) \leq O(2^{n^2})$$, not super-exponential; and since $$\sf NP \subseteq EXP$$, all problems in $$\sf NP$$ should be bounded by this "exponential time".

If you define "super-exponential" traditionally, i.e. $$2^{O(n)}$$: In this case, if you can find a $$\sf NP$$-complete problem $$A$$ that is not in $${\sf TIME}(2^{O(n)})$$, then it's not in $${\sf SPACE}(n)$$ either, thus we can know $${\sf NP} \nsubseteq {\sf SPACE}(n)$$; but it's still unknown that if $${\sf NP} \subseteq {\sf SPACE}(n)$$ now (maybe new results are published? I don't know, and I learn this from CMU 15-455 hw7 p4, spring 2017 by Prof. Ryan), so I guess proving this is hard.

(In fact this is more like a comment than an answer, but I don’t have enough reputation to do so, sorry about that)

• In literature, superexponetital quite often (but not exclusively) denotes non-single-exponential running time, i.e. running times not in $2^{O(n)}$. For example $O(n!) = O(n^n) = O(2^{n\log n})$ Commented Aug 1, 2022 at 15:29
• Thank you for pointing it out; and I have edited my answer for precision. Could you please check it out again? Thanks! Commented Aug 2, 2022 at 0:24
• Thanks for the answer and sorry for the slow response. As the above comment remarks, I define superexponential as something not in $2^{O(n)}$ (I call this just exponential time), since all the NP-complete problems I am aware of have worst case complexity in exponential time. Commented Aug 4, 2022 at 15:42
• I would not expect that $n$ alternations can save $O(n^k)$ time for an arbitrarily large $k$ for every problem in $NPC$, did not know that's not proven. Commented Jul 7, 2023 at 23:10