Suppose $P \neq NP$. Does it imply that there exists some superpolynomial time bound, such that any $NP$-complete problem, like SAT, can be used to simulate an arbitrary deterministc Turing Machine working in that time bound?

Rephrasing does $P \neq NP$ imply that there exists some class $D$ of languages solvable by a deterministic Turing Machine, such $P \subsetneq\ D \subseteq NP$ and SAT is $D$-hard?

  • 1
    $\begingroup$ $D$-hard under what kind of reduction? Since SAT is $NP$-hard, doesn't that automatically make SAT $D$-hard? Any language in $NP$ (and thus any language in $D$) can be reduced to SAT in polytime. $\endgroup$ – Tom van der Zanden May 4 '15 at 14:54
  • 1
    $\begingroup$ Your rephrasing sounds like a question that Ladner's Theorem answers. Or do you mean something else? $\endgroup$ – Kyle Jones May 4 '15 at 16:14

This post shows that the answer to your initial question is yes (even if P = NP).

On the other hand, I suspect there is no known proof that if unambiguousGC(polylog, NC) ⊈ coNP/poly then there is a superpolynomial time-constructible function $T$ and a superlogarithmic space-constructible function $S$ such that

DTIME(T(n)) ∩ DSPACE(S(n)) ⊆ NP/poly.

| cite | improve this answer | |
  • 2
    $\begingroup$ Dude. Stop formatting like that. How many times have the mods brought that up, now? $\endgroup$ – Nicholas Mancuso May 6 '15 at 4:35
  • $\begingroup$ I think once, on the meta thread. $\endgroup$ – user12859 May 6 '15 at 5:28
  • 3
    $\begingroup$ @RickyDemer I recall multiple instances in comments (may be gone by now). Seriously, just use Unicode math... $\endgroup$ – Raphael May 6 '15 at 6:48
  • $\begingroup$ @Raphael: Ah yes, you commented on the meta thread too. (I don't remember any other instance in which a mod brought that up.) $\endgroup$ – user12859 May 6 '15 at 6:55
  • 3
    $\begingroup$ @RickyDemer Oh, I don't know. Then consider this instance 2+x: please stop formatting like this. $\endgroup$ – Raphael May 6 '15 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.