20

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)$.

Community
  • 1
Anonymous
  • 201
  • 1
  • 2
  • 6
    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 Mar 13 '15 at 02:21
  • 2
    Just to restate the question: what is the largest $f$ where ExpTime$\subseteq$NTime$(f(n))$ implies NP$\not\subseteq$P? – Kaveh Mar 13 '15 at 03:29
  • ps: if you register an account you can edit your question more easily. – Kaveh Mar 13 '15 at 03:36
  • 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'$. – Joe Bebel Mar 13 '15 at 05:05

2 Answers2

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}$.

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
Russell Impagliazzo
  • 1,331
  • 10
  • 8
  • 1
    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 Mar 16 '15 at 08:34
  • And, thanks for pointing out that either the deterministic or non-deterministic time hierarchy theorem could be used. :) – Michael Wehar Mar 16 '15 at 08:58
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$?

Michael Wehar
  • 5,127
  • 1
  • 24
  • 54
  • 1
    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 Mar 13 '15 at 10:22
  • 1
    @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 Mar 13 '15 at 11:00