<p>I think its easier to turn it around.</p>

<p>If $\mathsf{P}=\mathsf{NP}$, then $\mathsf{NTIME}(T(n)) \subset \mathsf{DTIME} ((T(n))^c)$ 
for some constant $c$, and any $T(n) &gt; n$.
Since $\mathsf{DTIME} ((T(n)^c)$ does not contain 
$\mathsf{DTIME}(T(n)^{c}\log T(n)) \subset \mathsf{DTIME}(T(n)^{c+1})$, 
this means we cannot solve, say all problems in $\mathsf{DTIME}(2^n)$ in 
$\mathsf{NTIME} (2^{\epsilon n})$ for some $\epsilon$.
So a non-deterministic time $2^{o(n)}$ algorithm for a problem complete for
$\mathsf{DTIME} (2^n)$ under quasi-linear reductions would be enough to prove $\mathsf{P} \neq \mathsf{NP}$.</p>

CC BY-SA 3.0
2015-03-16T08:34:06.690Z
Thanks for taking the time to provide a briefer explanation of why $DTIME(2^n) \subseteq NTIME(2^{o(n)})$ implies $P \neq NP$.
Michael Wehar
CC BY-SA 3.0
2015-03-16T08:58:59.257Z
And, thanks for pointing out that either the deterministic or non-deterministic time hierarchy theorem could be used.  :)
Michael Wehar
CC BY-SA 3.0
2015-03-15T21:55:56.080Z
2015-03-15T22:43:08.813Z
2015-03-15T22:43:08.813Z
Russell Impagliazzo
<p><strong>Simple Answer:</strong> For each $EXPTIME$-$hard$ problem there is some constant $c$ such that if we could solve the problem in $NTIME(2^{o(n^{\frac{1}{c}})})$, then $P \neq NP$.</p>

<p>Note: The constant $c$ comes from the instance size blow-ups that result from the reductions.</p>

<p><strong>Justification:</strong> Let $X$ denote an $EXPTIME$-$hard$ problem.  That means that every problem in $EXPTIME$ is polynomial time reducible to $X$.  In fact, we can show more.</p>

<p>The acceptance problem for $2^n$ time bounded deterministic Turing machines is in $DTIME(n \cdot 2^n) \subseteq EXPTIME$ and therefore is polynomial time reducible to $X$.</p>

<p>Therefore, there must be some fixed constant $c$ such that every problem in $DTIME(2^n)$ is polynomial time reducible to $X$ where the instance size blow-up is $O(n^c)$.  That is, instances of size n are reduced to instances of size $O(n^c)$ for $X$.</p>

<p>Now, if we had $X \in NTIME(2^{o(n^{\frac{1}{c}})})$, then $DTIME(2^n) \subseteq NTIME(2^{o(n)})$.  However, this implies $P \neq NP$ (see below for details). </p>

<p><strong>Additional Details:</strong> One can show that $P=NP$ $\Leftrightarrow$ $\exists c^{\prime}$ $\forall k$ $NTIME(n^k) \subseteq DTIME(n^{c^{\prime}k})$.</p>

<p>In other words, if you can solve an $NP$-$complete$ problem in polynomial time, then there is a uniform way of speeding up any problem in $NP$.</p>

<p>Now, let's suppose that $P=NP$.  By the preceding (with $k$=1) we get a constant $c^{\prime}$ such that
$$NTIME(n) \subseteq DTIME(n^{c^{\prime}}).$$</p>

<p>Next, we can use padding to scale up this inclusion and get
$$NTIME(2^{n}) \subseteq DTIME(2^{c^{\prime}n}).$$</p>

<p>Then, by the deterministic time hierarchy theorem, we have
$$NTIME(2^{n}) \subseteq DTIME(2^{c^{\prime}n}) \subsetneq DTIME(2^{(c^{\prime}+\epsilon)n})$$
for any $\epsilon &gt; 0$.</p>

<p>Therefore, we couldn't have
$DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{n}).$</p>

<p>Further, we couldn't have $DTIME(2^{n}) \subseteq NTIME(2^{o(n)})$ because by padding we would get $DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{o(n)})$.</p>

<p><strong>Further Question:</strong> Does anyone have any simple examples of $EXPTIME$-$complete$ problems where we can easily determine the instance size blow-up constant $c$?</p>

CC BY-SA 3.0
2015-03-13T10:22:06.167Z
The acceptance problem for $DTIME(2^n)$ is itself $EXPTIME$-complete, that is, the language $L = \{\langle T, x, 1^m \rangle\}$ consisting of DTMs $T$ that on input $x$ accept within $2^m$ steps, because every language $L' \in EXPTIME$ has some $T$ that accepts $x \in L'$ in time $2^{O(|x|^k)})$ for some $k$, so that proper choice of $m = O(|x|^k)$ reduces $L'$ to $L$. In particular the constant ($c=1$) then seems to show that the speedup (that is, $f(n)$) must be exponential if to show $P \ne NP$, if you choose this particular $EXPTIME$-complete language.
Joe Bebel
CC BY-SA 3.0
2015-03-13T11:00:33.190Z
@JoeBebel Hi Joe, thanks for the comment.  I think it's valuable that you further considered this problem $L$.  Here, we can say more than just $L \in NTIME(2^{o(n)})$ implies $P \neq NP$.  For this particular artificial problem $L$, we may be able to say something like for any $k$, $L \in NTIME(2^{\frac{n}{k}})$ implies $NTIME(n) \nsubseteq DTIME(n^{k-\epsilon})$ for all $\epsilon > 0$.
Michael Wehar
CC BY-SA 3.0
2015-03-13T07:54:21.150Z
2015-03-16T08:54:57.533Z
2015-03-16T08:54:57.533Z
Michael Wehar
<p>How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$?  A polynomial time nondeterministic algorithm would immediately imply this because $P \neq EXPTIME$ but no one believes $NP = EXPTIME$.  If I've done the algebra right (see below) the time hierarchy theorem would still give the $P \neq NP$ implication for $O(2^n/f(n))$ running times for any superpolynomial $f(\cdot)$, but for all I know there are complete problems with efficient reductions that allow slower algorithms to give the result.  Are there EXPTIME-complete problems where we know something like $2^n/n$ or $2^n/n^2$ with nondeterminism is enough?</p>

<p>Clarification of the "algebra": $P = NP$ implies $EXPTIME=NEXPTIME$ by a padding argument, so a nondeterministic $2^n/f(n)$ algorithm for an EXPTIME-complete problem would also be one for a NEXPTIME-complete problem.  For superpolynomial $f(\cdot)$ this would contradict the nondeterministic time hierarchy theorem since we could reduce using some $L \in$ NTIME$(2^n)$.</p>

CC BY-SA 3.0
2015-03-13T02:21:23.393Z
I think you actually need running time $2^{n^{o(1)}}$ to get a contradiction from the time hierarchy theorem. Also I think this sounds quite unlikely.
Sasho Nikolov
CC BY-SA 3.0
2015-03-13T03:29:37.140Z
Just to restate the question: what is the largest $f$ where ExpTime$\subseteq$NTime$(f(n))$ implies NP$\not\subseteq$P?
Kaveh
CC BY-SA 3.0
2015-03-13T03:36:25.820Z
ps: if you register an account you can edit your question more easily.
Kaveh
CC BY-SA 3.0
2015-03-13T05:05:37.153Z
I believe Sasho is correct, if $EXPTIME=NEXPTIME$ such that $L$ is $EXPTIME$-complete and $L'$ is $NEXPTIME$-complete and $L'$ is reducible to $L$ in time $O(n^k)$, then it's still possible that $L \in NTIME(2^{\sqrt[k]{n}})$ without any contradiction because the instance of $L$ may be $O(n^k)$ larger than $L'$.
Joe Bebel
<cc.complexity-theory>
How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$?
Anonymous
# How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$?

(Asked by: username_0 on 2015-03-13)

How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$? A polynomial time nondeterministic algorithm would immediately imply this because $P \neq EXPTIME$ but no one believes $NP = EXPTIME$. If I've done the algebra right (see below) the time hierarchy theorem would still give the $P \neq NP$ implication for $O(2^n/f(n))$ running times for any superpolynomial $f(\cdot)$, but for all I know there are complete problems with efficient reductions that allow slower algorithms to give the result. Are there EXPTIME-complete problems where we know something like $2^n/n$ or $2^n/n^2$ with nondeterminism is enough?

Clarification of the "algebra": $P = NP$ implies $EXPTIME=NEXPTIME$ by a padding argument, so a nondeterministic $2^n/f(n)$ algorithm for an EXPTIME-complete problem would also be one for a NEXPTIME-complete problem. For superpolynomial $f(\cdot)$ this would contradict the nondeterministic time hierarchy theorem since we could reduce using some $L \in$ NTIME$(2^n)$.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: I think you actually need running time $2^{n^{o(1)}}$ to get a contradiction from the time hierarchy theorem. Also I think this sounds quite unlikely.  
> **username_2**: Just to restate the question: what is the largest $f$ where ExpTime$\subseteq$NTime$(f(n))$ implies NP$\not\subseteq$P?  
> **username_2**: ps: if you register an account you can edit your question more easily.  
> **username_3**: I believe Sasho is correct, if $EXPTIME=NEXPTIME$ such that $L$ is $EXPTIME$-complete and $L'$ is $NEXPTIME$-complete and $L'$ is reducible to $L$ in time $O(n^k)$, then it's still possible that $L \in NTIME(2^{\sqrt[k]{n}})$ without any contradiction because the instance of $L$ may be $O(n^k)$ larger than $L'$.  

---

## 2 answers

### Answer by username_4 on 2015-03-15. Score: 16

I think its easier to turn it around.

If $\mathsf{P}=\mathsf{NP}$, then $\mathsf{NTIME}(T(n)) \subset \mathsf{DTIME} ((T(n))^c)$
for some constant $c$, and any $T(n) > n$.
Since $\mathsf{DTIME} ((T(n)^c)$ does not contain
$\mathsf{DTIME}(T(n)^{c}\log T(n)) \subset \mathsf{DTIME}(T(n)^{c+1})$,
this means we cannot solve, say all problems in $\mathsf{DTIME}(2^n)$ in
$\mathsf{NTIME} (2^{\epsilon n})$ for some $\epsilon$.
So a non-deterministic time $2^{o(n)}$ algorithm for a problem complete for
$\mathsf{DTIME} (2^n)$ under quasi-linear reductions would be enough to prove $\mathsf{P} \neq \mathsf{NP}$.

> **Comments:**
> **username_5**: Thanks for taking the time to provide a briefer explanation of why $DTIME(2^n) \subseteq NTIME(2^{o(n)})$ implies $P \neq NP$.  
> **username_5**: And, thanks for pointing out that either the deterministic or non-deterministic time hierarchy theorem could be used.  :)  

---

### Answer by username_5 on 2015-03-13. Score: 15

**Simple Answer:** For each $EXPTIME$-$hard$ problem there is some constant $c$ such that if we could solve the problem in $NTIME(2^{o(n^{\frac{1}{c}})})$, then $P \neq NP$.

Note: The constant $c$ comes from the instance size blow-ups that result from the reductions.

**Justification:** Let $X$ denote an $EXPTIME$-$hard$ problem. That means that every problem in $EXPTIME$ is polynomial time reducible to $X$. In fact, we can show more.

The acceptance problem for $2^n$ time bounded deterministic Turing machines is in $DTIME(n \cdot 2^n) \subseteq EXPTIME$ and therefore is polynomial time reducible to $X$.

Therefore, there must be some fixed constant $c$ such that every problem in $DTIME(2^n)$ is polynomial time reducible to $X$ where the instance size blow-up is $O(n^c)$. That is, instances of size n are reduced to instances of size $O(n^c)$ for $X$.

Now, if we had $X \in NTIME(2^{o(n^{\frac{1}{c}})})$, then $DTIME(2^n) \subseteq NTIME(2^{o(n)})$. However, this implies $P \neq NP$ (see below for details).

**Additional Details:** One can show that $P=NP$ $\Leftrightarrow$ $\exists c^{\prime}$ $\forall k$ $NTIME(n^k) \subseteq DTIME(n^{c^{\prime}k})$.

In other words, if you can solve an $NP$-$complete$ problem in polynomial time, then there is a uniform way of speeding up any problem in $NP$.

Now, let's suppose that $P=NP$. By the preceding (with $k$=1) we get a constant $c^{\prime}$ such that
$$NTIME(n) \subseteq DTIME(n^{c^{\prime}}).$$

Next, we can use padding to scale up this inclusion and get
$$NTIME(2^{n}) \subseteq DTIME(2^{c^{\prime}n}).$$

Then, by the deterministic time hierarchy theorem, we have
$$NTIME(2^{n}) \subseteq DTIME(2^{c^{\prime}n}) \subsetneq DTIME(2^{(c^{\prime}+\epsilon)n})$$
for any $\epsilon > 0$.

Therefore, we couldn't have
$DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{n}).$

Further, we couldn't have $DTIME(2^{n}) \subseteq NTIME(2^{o(n)})$ because by padding we would get $DTIME(2^{(c^{\prime}+\epsilon)n}) \subseteq NTIME(2^{o(n)})$.

**Further Question:** Does anyone have any simple examples of $EXPTIME$-$complete$ problems where we can easily determine the instance size blow-up constant $c$?

> **Comments:**
> **username_3**: The acceptance problem for $DTIME(2^n)$ is itself $EXPTIME$-complete, that is, the language $L = \{\langle T, x, 1^m \rangle\}$ consisting of DTMs $T$ that on input $x$ accept within $2^m$ steps, because every language $L' \in EXPTIME$ has some $T$ that accepts $x \in L'$ in time $2^{O(|x|^k)})$ for some $k$, so that proper choice of $m = O(|x|^k)$ reduces $L'$ to $L$. In particular the constant ($c=1$) then seems to show that the speedup (that is, $f(n)$) must be exponential if to show $P \ne NP$, if you choose this particular $EXPTIME$-complete language.  
> **username_5**: @JoeBebel Hi Joe, thanks for the comment.  I think it's valuable that you further considered this problem $L$.  Here, we can say more than just $L \in NTIME(2^{o(n)})$ implies $P \neq NP$.  For this particular artificial problem $L$, we may be able to say something like for any $k$, $L \in NTIME(2^{\frac{n}{k}})$ implies $NTIME(n) \nsubseteq DTIME(n^{k-\epsilon})$ for all $\epsilon > 0$.  

---

