¿Se puede resolver cualquier problema NP-Complete utilizando como máximo espacio polinomial (pero utilizando el tiempo exponencial?)

12

Leí acerca de NPC y su relación con PSPACE y deseo saber si los problemas de NPC se pueden resolver de manera determinista utilizando un algoritmo con el requisito de espacio polinomial en el peor de los casos, pero potencialmente tomando tiempo exponencial (2 ^ P (n) donde P es polinomial).

Además, ¿se puede generalizar a EXPTIME en general?

La razón por la que pregunto esto es que escribí algunos programas para resolver casos degenerados de un problema de NPC, y pueden consumir cantidades muy grandes de RAM para instancias difíciles, y me pregunto si hay una mejor manera. Para referencia, consulte https://fc-solve.shlomifish.org/faq.html .

Shlomi Fish
fuente

Respuestas:

27

En términos generales, lo siguiente es cierto para cualquier algoritmo:

  1. Supongamos que A es un algoritmo que se ejecuta en tiempo f(n) . Entonces A no podía tomar más de f(n) el espacio, ya que la escritura f(n) bits de requiere f(n) tiempo.
  2. Supongamos que A es un algoritmo que requiere espacio f(n) . Luego, en 2f(n) tiempo, A puede visitar cada uno de sus diferentes estados, por lo tanto, no puede ganar nada al ejecutar más de 2f(n) tiempo.

Resulta que:

NP PSPACE

La declaración se conoce como parte de las relaciones entre las clases, como se muestra en el siguiente diagrama:

relaciones entre clases

La explicación es simple: un problema Q NP tiene un certificado de longitud polinómica y . Un algoritmo que prueba todos los certificados posibles es un algoritmo que decide Q en el tiempo 2nO(1) .

Su espacio requerido es:

  • y (polinomio enn )
  • yy

Q


Ejemplo:

φx1xnmff:{x1xn}{0,1}

Sostiene que:

  • 2n
  • fO(m)φO(m)

A

Resulta que:

PSPACENP PSPACE

salmón ahumado
fuente
1
¿Por qué están relacionados EXPSPACE y EXPTIME? Pensé que el tiempo y el espacio eran recursos diferentes. Un ejemplo que viene a la mente es romper un esquema de cifrado, que requeriría EXPTIME, pero un espacio constante
WeCanBeFriends
66
f(n)f(n)2f(n)
¿Es f (n) diferente a O (n) en su ejemplo?
WeCanBeFriends
1
@WeCanBeFriends No se puede emplear tiempo exponencial con espacio constante: se necesita al menos el espacio utilizado para contar hasta ese número exponencial (por ejemplo, el contador de programa de un lenguaje ensamblador), que es polinomial (logarítmico en el exponencial)
gigabytes
44
PEXPTIME
9

Si. Aquí hay un boceto de una prueba directa.

NPMpMnp(n)p(n)

cMMccp(n)ncp(n)p(n)cp(n)Miii6

00Mc1cp(n)p(n)2p(n)

David Richerby
fuente