20
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Mar 13, 2015 at 2:21
  • 2
    $\begingroup$ Just to restate the question: what is the largest $f$ where ExpTime$\subseteq$NTime$(f(n))$ implies NP$\not\subseteq$P? $\endgroup$
    – Kaveh
    Mar 13, 2015 at 3:29
  • $\begingroup$ ps: if you register an account you can edit your question more easily. $\endgroup$
    – Kaveh
    Mar 13, 2015 at 3:36
  • 3
    $\begingroup$ 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'$. $\endgroup$
    – Joe Bebel
    Mar 13, 2015 at 5:05

2 Answers 2

Reset to default
16
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks for taking the time to provide a briefer explanation of why $DTIME(2^n) \subseteq NTIME(2^{o(n)})$ implies $P \neq NP$. $\endgroup$
    – Michael Wehar
    Mar 16, 2015 at 8:34
  • $\begingroup$ And, thanks for pointing out that either the deterministic or non-deterministic time hierarchy theorem could be used. :) $\endgroup$
    – Michael Wehar
    Mar 16, 2015 at 8:58
15
$\begingroup$

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$?

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joe Bebel
    Mar 13, 2015 at 10:22
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Michael Wehar
    Mar 13, 2015 at 11:00

Your Answer

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

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