7
$\begingroup$

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.

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

1 Answer 1

5
$\begingroup$

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)

$\endgroup$
4
  • 1
    $\begingroup$ 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})$ $\endgroup$ Commented Aug 1, 2022 at 15:29
  • 1
    $\begingroup$ Thank you for pointing it out; and I have edited my answer for precision. Could you please check it out again? Thanks! $\endgroup$
    – Heda Chen
    Commented Aug 2, 2022 at 0:24
  • $\begingroup$ 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. $\endgroup$
    – user918212
    Commented Aug 4, 2022 at 15:42
  • $\begingroup$ 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. $\endgroup$
    – rus9384
    Commented Jul 7, 2023 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.