¿Implicaciones entre

10

Si podemos demostrar que , ¿implica que ?N L = N PL=PNL=NP

Pensé que era el caso, pero no puedo probarlo (también por el contrario).

cc.complexity-theory complexity-classes nondeterminism Thatchaphol
fuente
3
Probar lo contrario sería bastante difícil ...
domotorp 05 de
Lo inverso se reduce a si NL = P implica L = P. Esto no es necesariamente cierto a menos que L = NL.
Mohammad Al-Turkistany
1
Publiqué una pregunta relacionada sobre las relaciones entre P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L. Si está interesado, no dude en echar un vistazo. ¡Gracias! cstheory.stackexchange.com/questions/31073/…
Michael Wehar

Respuestas:

14

No. Es posible que L = P y que P! = NP, lo que implica que NL! = NP ya que NL está contenido en P.

Mohammad Al-Turkistany
fuente
55
Creo que probablemente sería útil, en lugar de simplemente afirmar esto directamente, dar una idea de cómo podría ser esto. Considerando la construcción NP = ∃P (es decir, su definición en términos de verificar un testigo usando un algoritmo de polytime), puedo ver cómo uno podría adivinar que si P = L , simplemente podríamos obtener NP = ∃L = NL por sustitución. Quizás algunas observaciones sobre cómo la limitación logarítmica en la cinta de trabajo ayudaría a indicar por qué este no es el caso.
Niel de Beaudrap