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

CC BY-SA 3.0
2013-08-15T15:19:06.873Z
Have you tried "generate a possible solution then check it in polynomial time"?
András Salamon
CC BY-SA 3.0
2013-08-15T15:23:14.237Z
Note that $n!=2^{O(n \log(n))}$, so it is not much worse than $c^n$.
Igor Shinkar
CC BY-SA 3.0
2013-08-15T15:25:30.277Z
Also, if the reduction from your problem to SAT takes linear time, then your problem can be solved in $c^n$ time.
Igor Shinkar
CC BY-SA 3.0
2013-08-15T18:07:04.687Z
The upper bound on NP is $2^{n^{O(1)}}$ which is called exponential.
Kaveh
CC BY-SA 3.0
2013-08-15T20:43:42.417Z
Note that $n!=2^{\Omega(n\log n)}$, so it is quite a bit worse than $c^n$.
Jeffε
CC BY-SA 3.0
2013-08-15T22:21:21.113Z
there must be some way to show that conditional on the ETH there exist problems in NP that take time at least $2^{n^c}$ for an infinite sequence of integers $c$. on the other hand $\mathsf{P} \neq \mathsf{NP}$ as far as I know could be consistent with $\mathsf{NP} \subseteq \mathsf{DTIME}(n^{\log^* n})$
Sasho Nikolov
CC BY-SA 3.0
2013-08-16T06:02:43.710Z
@Sasho: "given an NTM $M$ and a unary number $n$, does $M$ halt in $n^c$ steps?"
Kaveh
CC BY-SA 3.0
2013-08-17T23:16:48.333Z
Why don't you ask a question where you describe your specific problem?
D.W.
<upper-bounds><np-complete>
Are there upper bounds on the worst case complexity of NP-complete problems?
user1742364
# Are there upper bounds on the worst case complexity of NP-complete problems?

(Asked by: username_0 on 2013-08-15)

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

**Tags:** upper-bounds, np-complete

> **Comments:**
> **username_1**: Have you tried "generate a possible solution then check it in polynomial time"?  
> **username_2**: Note that $n!=2^{O(n \log(n))}$, so it is not much worse than $c^n$.  
> **username_2**: Also, if the reduction from your problem to SAT takes linear time, then your problem can be solved in $c^n$ time.  
> **username_3**: The upper bound on NP is $2^{n^{O(1)}}$ which is called exponential.  
> **username_4**: Note that $n!=2^{\Omega(n\log n)}$, so it is quite a bit worse than $c^n$.  
> **username_5**: there must be some way to show that conditional on the ETH there exist problems in NP that take time at least $2^{n^c}$ for an infinite sequence of integers $c$. on the other hand $\mathsf{P} \neq \mathsf{NP}$ as far as I know could be consistent with $\mathsf{NP} \subseteq \mathsf{DTIME}(n^{\log^* n})$  
> **username_3**: @Sasho: "given an NTM $M$ and a unary number $n$, does $M$ halt in $n^c$ steps?"  
> **username_6**: Why don't you ask a question where you describe your specific problem?  

---

## 0 answers

