Wie schnell müsste ein nicht deterministischer Algorithmus für ein EXPTIME-vollständiges Problem sein, um

Wie schnell müsste ein nicht deterministischer Algorithmus für ein EXPTIME-vollständiges Problem sein, um zu implizieren ? Ein nicht deterministischer Algorithmus für die Polynomzeit würde dies sofort implizieren, da aber niemand glaubt . Wenn ich die Algebra richtig gemacht hätte (siehe unten), würde der Zeithierarchiesatz immer noch die Implikation für Laufzeiten für jedes Superpolynom , aber für Ich weiß nur, dass es vollständige Probleme mit effizienten Reduktionen gibt, die es langsameren Algorithmen ermöglichen, das Ergebnis zu liefern. Gibt es EXPTIME-vollständige Probleme, bei denen wir so etwas wie oder kennen?$P \neq NP$$P \neq EXPTIME$$NP = EXPTIME$$P \neq NP$$O(2^n/f(n))$$f(\cdot)$$2^n/n$$2^n/n^2$ mit Nichtdeterminismus ist genug?

Klärung der "Algebra": impliziert durch ein Auffüllargument, daher wäre ein nicht deterministischer -Algorithmus für ein EXPTIME-vollständiges Problem auch einer für ein NEXPTIME-vollständiges Problem. Für das Superpolynom würde dies dem nichtdeterministischen Zeithierarchiesatz widersprechen, da wir mit einigem NTIME reduzieren könnten .$P = NP$$EXPTIME=NEXPTIME$$2^n/f(n)$$f(\cdot)$$L \in$$(2^n)$

Ich denke, es ist einfacher, es umzudrehen.

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

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

Next, we can use padding to scale up this inclusion and get

Then, by the deterministic time hierarchy theorem, we have

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