0
$\begingroup$

Suppose $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ then is it true $P=NP$ holds?

Ladner's theorem states infinite time hierarchy between $P$ and $NP$. That is there are $NP$ problems in $DTIME[n^{g(n)}]$ for any $g(n)$ such that $n^c\leq n^{g(n)}\leq 2^{n^{1/c}}$ at some fixed $c\geq1$. If $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ then for every such $g(n)$ we can find a $f(n)\ll g(n)$ and so Ladner's theorem is violated and so $P=NP$ has to hold.

And so if $P\neq NP$ there is $g(n)$ with $n^c\leq n^{g(n)}\leq 2^{n^{1/c}}$ such that $NP\subsetneq DTIME[n^{g(n)}]$ and $NP\subseteq DTIME[n^{f(n)}]$ where $f(n)$ is any function satisfying $\omega(1)$ implies $P=NP$. Are these observations correct?

What if I replace $DTIME$ by $RTIME$? Would this yield $RP=NP$ by some randomized version Ladner's theorem?

$\endgroup$
3
$\begingroup$

I'm annoyed at both ["any" being used as a quantifier] and [the placement of quantifiers making things even more ambiguous], so I'll start with the two interpretations of your initial block-quote.

Suppose there is a function $\hspace{.04 in}f$ in $\omega(1)$ such that ​ NP $\subseteq$ DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right]$ .
Does it follow that ​ P = NP ?

It's not known to, since ​ ​ ​ ($n\mapsto 2^{\hspace{.02 in}n}\hspace{-0.03 in}$) ​ $\in$ ​ $\omega(1)$ ​ ​ ​ and ​ NP $\subseteq$ EXP $\subseteq$ DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}(2^{\hspace{.02 in}n})}\hspace{-0.04 in}\right]$ ​ are both known.

Suppose that for all functions $\hspace{.04 in}f$ in $\omega(1)$, ​ NP $\subseteq$ DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right]$ .
Does it follow that ​ P = NP ?

Yes, since as described in this answer, there exists
a function $\hspace{.04 in}f$ in $\omega(1)$ such that ​ DTIME$\left[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right]$ = P .


The truth of your "That is ... fixed $c\geq 1$." sentence has nothing to do with Ladner's Theorem
- The empty language and full language, for example, are such NP problems.
For the sentence after that, the g given by ​ g(n) = c ​ is such a g, and functions f cannot simultaneously be in $\omega(1)$ and satisfy ​ f(n) << c , ​ so where's the violation of Ladner's theorem?
By the function g I just mentioned, the part of your
"And so if ..." sentence before that sentence's "and" is true.
For the rest of that sentence, see this answer's two block-quotes and its responses to those.


This answer's response to its "there is" block-quote would still apply.
I believe this answer's response to its "for all" block-quote
would also still apply, by a similar argument.

$\endgroup$
  • $\begingroup$ the link you posted was exactly what I am looking for. $\endgroup$ – T.... Oct 24 '16 at 1:55

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.