<p>I've asked a <a href="https://cs.stackexchange.com/questions/22511/runtime-bounds-on-algorithms-of-np-complete-problems-assuming-problems-pnp">similar question</a> in cs.se, but didn't get a satisfying answer.</p>

<p>Assuming $P\neq NP$, what can we say about the runtime of any algorithm for an $NP$-complete problem?</p>

<p>Obviously, it means $\omega(n^c)$ for all $c&gt;0$, but can we give a better lower bound?
For example, is it possible that $P\neq NP$ and $NP\subset DTIME(2^{logn\cdot log^*n})$, where $log^*n$ is the <a href="http://en.wikipedia.org/wiki/Iterated_logarithm" rel="nofollow noreferrer">iterated log</a> function?</p>

CC BY-SA 3.0
2014-03-16T16:17:38.400Z
I would suggest fixing an NP-complete problem like SAT in place of using the whole class: what is the best lower-bound for SAT assuming SAT is not in P?
Kaveh
CC BY-SA 3.0
2014-03-17T04:36:25.313Z
My answer on cs.se shows that $NP=DTIME(2^{O(\log^2 n)})$ holds relative to a certain oracle (if the proof works), and the same method with a slight change of parameters should also show that $NP=DTIME(2^{O(\log n \log^* n)})$ relative to a certain oracle. Relative to another oracle, the exponential time hypothesis holds.
Yuval Filmus
CC BY-SA 3.0
2014-03-17T04:50:14.560Z
Why are you unhappy with the answer you got? An oracle separation (I haven't tried to verify Yuval's construction btw) usually is pretty good evidence that we do not know which of the relativized worlds is the truth.
Sasho Nikolov
CC BY-SA 3.0
2014-03-17T17:57:35.410Z
you're pushing the boundaries of current knowledge, is that what you refer to as "unsatisfying"? that seemingly basic separations are unknown? most TCS experts would agree with you on that, some go farther & even call it "embarrassing" etc! the next small step would be a novel or near breakthru result/thm... the stronger NP$\neq$P/poly is routinely conjectured but is not implied by P$\neq$NP so far as anyone knows.
vzn
CC BY-SA 3.0
2014-03-17T19:32:45.500Z
It's not that I disagree with Yuval's answer, but it didn't quite answer my question. It showed that it could be that $NP\subseteq QP$, and not a general bound.

Can the $BGS$ argument be used for every function $f(n)$ between the bounds I gave there such that $NP=DTIME(f(n))$ for some oracle?

I didn't by any means meant to offend Yuval or any other TCS expert. Yuval, you have my sincere apology.
R B
CC BY-SA 3.0
2014-03-17T20:54:04.623Z
You're not offending anybody, it's just that you didn't explain why *exactly* you're not happy with the answer. That is, until this comment. I suggest you read the original BGS argument (linked to in my answer), and then my variant. Assuming that my proof works, you should be able to answer your own question. (Note that you want $NP=\mathrm{DTIME}(f(n)^{O(1)})$.)
Yuval Filmus
CC BY-SA 3.0
2014-03-17T22:01:06.480Z
Thanks Yuval. Did you mean $NP=DTIME(f(n^{O(1)}))$?
R B
CC BY-SA 3.0
2014-03-18T01:34:05.610Z
@RB Yes, I guess that makes more sense.
Yuval Filmus
<cc.complexity-theory><complexity-classes><time-complexity><np><p-vs-np>
Does $P\neq NP$ imply any larger separation?
R B
# Does $P\neq NP$ imply any larger separation?

(Asked by: username_0 on 2014-03-16)

I've asked a [similar question](https://cs.stackexchange.com/questions/22511/runtime-bounds-on-algorithms-of-np-complete-problems-assuming-problems-pnp) in cs.se, but didn't get a satisfying answer.

Assuming $P\neq NP$, what can we say about the runtime of any algorithm for an $NP$-complete problem?

Obviously, it means $\omega(n^c)$ for all $c>0$, but can we give a better lower bound?
For example, is it possible that $P\neq NP$ and $NP\subset DTIME(2^{logn\cdot log^\*n})$, where $log^\*n$ is the [iterated log](http://en.wikipedia.org/wiki/Iterated_logarithm) function?

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, np, p-vs-np

> **Comments:**
> **username_1**: I would suggest fixing an NP-complete problem like SAT in place of using the whole class: what is the best lower-bound for SAT assuming SAT is not in P?  
> **username_2**: My answer on cs.se shows that $NP=DTIME(2^{O(\log^2 n)})$ holds relative to a certain oracle (if the proof works), and the same method with a slight change of parameters should also show that $NP=DTIME(2^{O(\log n \log^* n)})$ relative to a certain oracle. Relative to another oracle, the exponential time hypothesis holds.  
> **username_3**: Why are you unhappy with the answer you got? An oracle separation (I haven't tried to verify Yuval's construction btw) usually is pretty good evidence that we do not know which of the relativized worlds is the truth.  
> **username_4**: you're pushing the boundaries of current knowledge, is that what you refer to as "unsatisfying"? that seemingly basic separations are unknown? most TCS experts would agree with you on that, some go farther & even call it "embarrassing" etc! the next small step would be a novel or near breakthru result/thm... the stronger NP$\neq$P/poly is routinely conjectured but is not implied by P$\neq$NP so far as anyone knows.  
> **username_0**: It's not that I disagree with Yuval's answer, but it didn't quite answer my question. It showed that it could be that $NP\subseteq QP$, and not a general bound.  Can the $BGS$ argument be used for every function $f(n)$ between the bounds I gave there such that $NP=DTIME(f(n))$ for some oracle?  I didn't by any means meant to offend Yuval or any other TCS expert. Yuval, you have my sincere apology.  
> **username_2**: You're not offending anybody, it's just that you didn't explain why *exactly* you're not happy with the answer. That is, until this comment. I suggest you read the original BGS argument (linked to in my answer), and then my variant. Assuming that my proof works, you should be able to answer your own question. (Note that you want $NP=\mathrm{DTIME}(f(n)^{O(1)})$.)  
> **username_0**: Thanks Yuval. Did you mean $NP=DTIME(f(n^{O(1)}))$?  
> **username_2**: @RB Yes, I guess that makes more sense.  

---

## 0 answers

