¿Qué tan rápido debería ser un algoritmo no determinista para un problema completo EXPTIME para implicar

¿Qué tan rápido debería ser un algoritmo no determinista para un problema completo EXPTIME para implicar ? Un algoritmo no determinista de tiempo polinómico implicaría esto inmediatamente porque pero nadie cree que . Si he hecho el álgebra a la derecha (ver más abajo), el teorema de la jerarquía del tiempo todavía daría la implicación para los tiempos de ejecución para cualquier superpolinomio , pero para Todo lo que sé es que hay problemas completos con reducciones eficientes que permiten que algoritmos más lentos den el resultado. ¿Hay problemas-EXPTIME completa en los que sabemos algo así como o $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$ con el no determinismo es suficiente?

Aclaración del "álgebra": implica por un argumento de relleno, por lo que un algoritmo no determinista para un problema de EXPTIME-complete también sería uno para un problema de NEXPTIME-complete. Para el superpolinomio esto contradiría el teorema de la jerarquía de tiempo no determinista ya que podríamos reducir el uso de algo de NTIME . $P = NP$ $EXPTIME=NEXPTIME$ $2^n/f(n)$ $f(\cdot)$ $L \in$ $(2^n)$

cc.complexity-theory Anónimo
fuente

Creo que realmente necesita el tiempo de funcionamiento

para obtener una contradicción desde el teorema de la jerarquía temporal. También creo que esto suena bastante improbable. 2no(1) $2^{n^{o(1)}}$

Sasho Nikolov

Solo para repetir la pregunta: ¿cuál es la

más grande donde ExpTime

NTime

implica NP

P? f $f$

⊆ $\subseteq$

(f(n)) $(f(n))$

⊈ $\not\subseteq$

Kaveh

ps: si registra una cuenta, puede editar su pregunta más fácilmente.

Kaveh

Creo que Sasho es correcto, si

modo que

-completo y

es reducible a

en el tiempo

, entonces todavía es posible que

EXPTIME=NEXPTIME $EXPTIME=NEXPTIME$

L $L$

EXPTIME $EXPTIME$

L′ $L'$

NEXPTIME $NEXPTIME$

L′ $L'$

L $L$

O(nk) $O(n^k)$

sin ninguna contradicción porque la instancia de

puede ser

mayor que

. L∈NTIME(2n√k) $L \in NTIME(2^{\sqrt[k]{n}})$

L $L$

O(nk) $O(n^k)$

L′ $L'$

Joe Bebel

Respuestas:

Creo que es más fácil darle la vuelta.

Si , entonces para alguna constante , y cualquier . Como no contiene $\mathsf{P}=\mathsf{NP}$ $\mathsf{NTIME}(T(n)) \subset \mathsf{DTIME} ((T(n))^c)$ $c$ $T(n) > n$ $\mathsf{DTIME} ((T(n)^c)$ , esto significa que no podemos resolver, digamos todos los problemas en en para algunos $\mathsf{DTIME}(T(n)^{c}\log T(n)) \subset \mathsf{DTIME}(T(n)^{c+1})$ $\mathsf{DTIME}(2^n)$ $\mathsf{NTIME} (2^{\epsilon n})$ $\epsilon$ . Por lo que un no-determinista de tiempo algoritmo para un completo problema para en virtud de la reducción de cuasi-lineal sería suficiente para demostrar . $2^{o(n)}$ $\mathsf{DTIME} (2^n)$ $\mathsf{P} \neq \mathsf{NP}$

Russell Impagliazzo
fuente

Gracias por tomarse el tiempo para proporcionar una explicación breve de por qué

implica

. DTIME(2n)⊆NTIME(2o(n)) $DTIME(2^n) \subseteq NTIME(2^{o(n)})$

P≠NP $P \neq NP$

Michael Wehar

Y, gracias por señalar que podría usarse el teorema de la jerarquía de tiempo determinista o no determinista. :)

Michael Wehar

Respuesta simple: Para cada problema - hay una constante tal que si pudiéramos resolver el problema en $EXPTIME$ $hard$ $c$ , entonces. $NTIME(2^{o(n^{\frac{1}{c}})})$ $P \neq NP$

Nota: La constante proviene de las ampliaciones de tamaño de instancia que resultan de las reducciones. $c$

Justificación: Sea un problema - . Eso significa que todos los problemas de es polinomio irreducible tiempo para . De hecho, podemos mostrar más. $X$ $EXPTIME$ $hard$ $EXPTIME$ $X$

El problema de aceptación para tiempo limitado máquinas de Turing deterministas está en y por lo tanto es reducible tiempo polinómico a . $2^n$ $DTIME(n \cdot 2^n) \subseteq EXPTIME$ $X$

Por lo tanto, debe haber alguna constante fija modo que cada problema en sea polinomial reducible en tiempo a donde el tamaño de instancia es . Eso es, los casos de tamaño n se reducen a los casos de tamaño para . $c$ $DTIME(2^n)$ $X$ $O(n^c)$ $O(n^c)$ $X$

Ahora, si tuviéramos $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

N T I M E (n) \subseteq D T I M E (n c') .

$NTIME(n) \subseteq DTIME(n^{c^{\prime}}).$

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

N T I M E (2 n) \subseteq D T I M E (2 c' n) .

$NTIME(2^{n}) \subseteq DTIME(2^{c^{\prime}n}).$

Then, by the deterministic time hierarchy theorem, we have

N T I M E (2 n) \subseteq D T I M E (2 c' n) ⊊ D T I M E (2 (c' + ϵ) n)

$NTIME(2^{n}) \subseteq DTIME(2^{c^{\prime}n}) \subsetneq DTIME(2^{(c^{\prime}+\epsilon)n})$ for any

ϵ>0 $\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
fuente

The acceptance problem for

DTIME(2n) $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

@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