I've asked a similar question 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 function?

  • 2
    $\begingroup$ 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? $\endgroup$
    – Kaveh
    Mar 16 '14 at 16:17
  • $\begingroup$ 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. $\endgroup$ Mar 17 '14 at 4:36
  • 3
    $\begingroup$ 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. $\endgroup$ Mar 17 '14 at 4:50
  • 2
    $\begingroup$ 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. $\endgroup$
    – vzn
    Mar 17 '14 at 17:57
  • 2
    $\begingroup$ 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)})$.) $\endgroup$ Mar 17 '14 at 20:54

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.