# Are there upper bounds on the worst case complexity of NP-complete problems?

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)$.

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