Implicações entre e ?

Se pudermos provar que , isso implica que ? $\mathsf{L}=\mathsf{P}$ $\mathsf{NL}=\mathsf{NP}$

Eu pensei que era o caso, mas não posso provar (também para o inverso).

cc.complexity-theory complexity-classes nondeterminism Thatchaphol
fonte

Provando o contrário seria muito difícil ...

domotorp

O inverso se resume a saber se NL = P implica L = P. Isso não é necessariamente verdade, a menos que L = NL.

Mohammad Al-Turkistany

Publiquei uma pergunta relacionada sobre as relações entre P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L. Se você estiver interessado, não hesite em dar uma olhada. Obrigado! cstheory.stackexchange.com/questions/31073/...

Michael Wehar

Respostas:

Não. É possível que L = P e P! = NP, o que implica que NL! = NP, pois NL está contido em P.

Mohammad Al-Turkistany
fonte

Eu acho que provavelmente seria útil, em vez de meramente afirmar isso, dar alguma intuição de como isso poderia ser. Considerando a construção NP = ∃P (ou seja, sua definição em termos de verificação de uma testemunha usando um algoritmo polytime), posso ver como alguém poderia imaginar que, se P = L , poderíamos simplesmente obter NP = ∃L = NL por substituição. Talvez algumas observações sobre como a limitação logarítmica na fita de trabalho ajudem a indicar por que esse não é o caso.

Niel de Beaudrap