Implikacje między i ?

Jeśli możemy udowodnić, że , czy oznacza to, że ? $\mathsf{L}=\mathsf{P}$ $\mathsf{NL}=\mathsf{NP}$

Myślałem, że tak jest, ale nie mogę tego udowodnić (również w przypadku rozmowy).

cc.complexity-theory complexity-classes nondeterminism Thatchaphol
źródło

Udowodnienie rozmowy byłoby dość trudne ...

domotorp

Odwrotna sprowadza się do tego, czy NL = P implikuje L = P. To niekoniecznie jest prawdą, chyba że L = NL.

Mohammad Al-Turkistany

Zadałem powiązane pytanie dotyczące relacji między P a L, NP a NL, BPP a BPL, ⊕P i ⊕L. Jeśli jesteś zainteresowany, możesz rzucić okiem. Dziękuję Ci! cstheory.stackexchange.com/questions/31073/…

Michael Wehar

Odpowiedzi:

Nie. Możliwe, że L = P i to P! = NP, co oznacza, że NL! = NP, ponieważ NL jest zawarte w P.

Mohammad Al-Turkistany
źródło

Myślę, że byłoby bardziej pomocne niż zwykłe stwierdzenie tego, aby dać intuicję, jak to może być. Biorąc pod uwagę konstrukcję NP = ∃P (tj. Jej definicję w zakresie sprawdzania świadka za pomocą algorytmu czasu policyjnego), widzę, jak można się domyślić, że jeśli P = L , to możemy po prostu uzyskać NP = ∃L = NL przez podstawienie. Być może kilka uwag na temat tego, w jaki sposób ograniczenie logarytmiczne taśmy roboczej pomogłoby wskazać, dlaczego tak nie jest.

Niel de Beaudrap,