2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 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
    Commented May 4, 2015 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
    Commented May 4, 2015 at 16:14

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ Dude. Stop formatting like that. How many times have the mods brought that up, now? $\endgroup$
    – Nicholas Mancuso
    Commented May 6, 2015 at 4:35
  • $\begingroup$ I think once, on the meta thread. $\endgroup$
    – user12859
    Commented May 6, 2015 at 5:28
  • 3
    $\begingroup$ @RickyDemer I recall multiple instances in comments (may be gone by now). Seriously, just use Unicode math... $\endgroup$
    – Raphael
    Commented May 6, 2015 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
    Commented May 6, 2015 at 6:55
  • 3
    $\begingroup$ @RickyDemer Oh, I don't know. Then consider this instance 2+x: please stop formatting like this. $\endgroup$
    – Raphael
    Commented May 6, 2015 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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