I have proven some problem to be (weakly) NP-complete and try to find out some algorithm to solve it exactly. Except for some pseudo-polynomial stuff, I would be happy with an algorithm running in $O(c^n)$ for a constant $c$, but the best algorithm I can imagine runs in $O(n!)$, so much worse. Since all other NP-complete problems, where I know an exact algorithm, can be solved in exponential time, the question that comes to my mind is if there is some upper bound on the complexity of NP-complete problems like $O(c^n)$ or if there are problems with a proven lower bound of something like $O(n!)$, too (unless P = NP). At least everything is reducible to SAT, which in turn can be solved in $O(2^n)$.

  • 2
    $\begingroup$ Have you tried "generate a possible solution then check it in polynomial time"? $\endgroup$ Aug 15 '13 at 15:19
  • 3
    $\begingroup$ Also, if the reduction from your problem to SAT takes linear time, then your problem can be solved in $c^n$ time. $\endgroup$ Aug 15 '13 at 15:25
  • 2
    $\begingroup$ The upper bound on NP is $2^{n^{O(1)}}$ which is called exponential. $\endgroup$
    – Kaveh
    Aug 15 '13 at 18:07
  • 5
    $\begingroup$ Note that $n!=2^{\Omega(n\log n)}$, so it is quite a bit worse than $c^n$. $\endgroup$
    – Jeffε
    Aug 15 '13 at 20:43
  • 2
    $\begingroup$ @Sasho: "given an NTM $M$ and a unary number $n$, does $M$ halt in $n^c$ steps?" $\endgroup$
    – Kaveh
    Aug 16 '13 at 6:02

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.