Si el límite inferior de un problema es exponencial, ¿es NP?

Suponiendo que tenemos un problema $p$ y mostramos que el límite inferior para resolver $p$ es $\mathcal{\Omega}(2^n)$ .

¿puede el límite inferior $\mathcal{\Omega}(2^n)$ implica el problema en $NP$ ?

time-complexity np-complete kelalaka
fuente

No es NP pero es NP-hard.

usuario35734

¿Cómo sabes que es NP-hard?

Yuval Filmus

Si pudieras demostrar que un problema está tanto en

como en NP, habrías probado P

NP.

Ω (2^{n})

$\mathcal{\Omega}(2^n)$

\neq

$\neq$

Kasperd

@kasperd: A eso lo llamamos Rompecabezas de Merkle, pero debería excluirse de P =? NP porque la forma específica no produce otro con las mismas propiedades y una prueba de P = NP probablemente elimina cualquier forma de hacer Rompecabezas de Merkle que realmente funcione como destinado a. El tiempo exponencial de Merkle's Puzzles también es PSPACE para el usuario previsto.

Joshua

Los rompecabezas de @Joshua Merkle no son exponenciales en dependencia de la longitud de entrada . (Bueno, si suponemos que la solución para Alice es polinomial).

rus9384

Respuestas:

No. Por ejemplo, el problema de detención tiene un límite inferior de $\Omega(2^n)$ , pero no está en NP (ya que no es computable).

El teorema de la jerarquía de tiempo no determinista muestra que cualquier problema NEXP completo es otro ejemplo (con $2^n$ potencialmente reemplazado por una función exponencial más pequeña $c^{n^\epsilon}$ ).

NP es un límite superior de la complejidad de un problema.

Yuval Filmus
fuente

¿Podría dar un ejemplo de un problema que sea

pero no NP-hard?

Ω (2^{n})

$\Omega(2^n)$

Mario Carneiro

Puede construir tal problema usando la diagonalización.

Yuval Filmus

Lo siento, no te sigo. ¿Qué se está diagonalizando? ¿Estamos enumerando problemas o algoritmos? ¿Cómo sigue la dureza sin NP?

Mario Carneiro

2^{n}

$2^n$

No. Primero, como señala Yuval , el problema podría ser mucho más difícil que el límite inferior que has probado.

$\Theta(2^n)$ $\mathbf{NP}$ $\mathbf{P}=\mathbf{NP}$ $\mathrm{TIME}[\Omega(2^n)]$ $\mathbf{NP}$ $\mathbf{P}\neq\mathbf{NP}$ $\mathbf{NP}$

$\mathbf{NP}$ $\mathbf{NP}$

David Richerby
fuente