# $P \neq NP$ and determinism

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?

• $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. – Tom van der Zanden May 4 '15 at 14:54
• Your rephrasing sounds like a question that Ladner's Theorem answers. Or do you mean something else? – 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.

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