Si , entonces es ?

10

Si , entonces es ? Estoy haciendo esta pregunta porque, para otras clases no deterministas, parece que siempre establece que son iguales a sus contrapartes deterministas.P=NPL=NLP=NP

ttr
fuente

Respuestas:

15

Esta es una pregunta de investigación abierta. En nuestro estado actual de conocimiento, conocer no implicaría ni . Y, por el contrario, conocer o no implicaría nada sobre la pregunta vs . (Pero es posible que la prueba de vs nos diga algo sobre vs o viceversa.)P=NPL=NLLNLL=NLLNLPNPLNLPNP

Conocemos , donde la igualdad se deriva del teorema de Savitch . La versión no determinista del teorema de la jerarquía espacial dice que por lo que sabemos que al menos una de las inclusiones establecidas debe ser estricta. Creemos que son estrictos, pero nuestro conocimiento actual no descarta ningún subconjunto de ellos, siempre que incluya al menos uno entre y .LNLPNPPSPACE=NPSPACENLNPSPACENLPSPACE

David Richerby
fuente