Si

10

Si P=NP , alors L=NL ? Je pose cette question parce que, pour d'autres classes non déterministes, il semble que P=NP établit toujours qu'elles sont égales à leurs homologues déterministes.

ttr
la source

Réponses:

15

Il s'agit d'une question de recherche ouverte. À notre état actuel des connaissances, sachant serait ni laisser entendre L = N L , ni LN L . Et, à l' inverse, sachant L = N L ou LN L n'impliqueraient quoi que ce soit au sujet de la P vs N P question. (Mais il est possible que la preuve de L vs N L nous dise quelque chose sur P vs N PP=NPL=NLLNLL=NLLNLPNPLNLPNP ou vice versa.)

Nous connaissons , où l'égalité découle du théorème de Savitch . La version non déterministe du théorème de la hiérarchie spatiale dit que N LN P S P A C ELNLPNPPSPACE=NPSPACENLNPSPACEnous savons donc qu'au moins une des inclusions définies doit être stricte. Nous pensons qu'ils sont un peu strict , mais tous nos connaissances actuelles n'exclut pas un sous - ensemble d'entre eux, tant qu'il comprend au moins un entre et P S P A C E .NLPSPACE

David Richerby
la source