Are there superexponential NP-complete problems?

Question

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.

• Yuval Filmus: "Does nondeterministic Turing machine $M$ accept the empty input within time $|M|^{100}$" might qualify.

Answer 1

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)

• Narek Bojikian: 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})$
• Heda Chen: Thank you for pointing it out; and I have edited my answer for precision. Could you please check it out again? Thanks!
• user918212: 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.
• rus9384: 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.