Implications entre

Si nous pouvons prouver que , cela implique-t-il que ? $\mathsf{L}=\mathsf{P}$ $\mathsf{NL}=\mathsf{NP}$

Je pensais que c'était le cas, mais je ne peux pas le prouver (également pour l'inverse).

cc.complexity-theory complexity-classes nondeterminism Thatchaphol
la source

Il serait assez difficile de

prouver

L'inverse revient à savoir si NL = P implique L = P. Ce n'est pas nécessairement vrai à moins que L = NL.

Mohammad Al-Turkistany

J'ai posté une question connexe sur les relations entre P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L. Si vous êtes intéressé, n'hésitez pas à jeter un œil. Je vous remercie! cstheory.stackexchange.com/questions/31073/…

Michael Wehar

Réponses:

Non. Il est possible que L = P et que P! = NP ce qui implique que NL! = NP puisque NL est contenu dans P.

Mohammad Al-Turkistany
la source

Je pense qu'il serait probablement utile, plutôt que de simplement l'affirmer, de donner une idée de ce que cela pourrait être. En considérant la construction NP = ∃P (c'est-à-dire sa définition en termes de vérification d'un témoin à l'aide d'un algorithme de polytime), je peux voir comment on pourrait deviner que si P = L , on pourrait simplement obtenir NP = ∃L = NL par substitution. Peut-être quelques remarques sur la façon dont la limitation logarithmique de la bande de travail aiderait à indiquer pourquoi ce n'est pas le cas.

Niel de Beaudrap