Jeśli

Jeśli $\mathbf{P} = \mathbf{NP}$ , to czy $\mathbf{L} = \mathbf{NL}$ ? Zadaję to pytanie, ponieważ dla innych niedeterministycznych klas wydaje się, że $\mathbf{P} = \mathbf{NP}$ zawsze ustala, że ​​są one równe ich deterministycznym odpowiednikom.

To otwarte pytanie badawcze. Na naszym aktualnym stanem wiedzy, wiedząc, byłoby ani sugerować L = N L ani L ≠ N L . I odwrotnie, znajomość L = N L lub L ≠ N L nie sugerowałoby niczego w kwestii pytania P vs N P. (Ale to jest możliwe, że dowód z L vs N L powie nam coś o P vs N $\mathbf{P}=\mathbf{NP}$$\mathbf{L}=\mathbf{NL}$$\mathbf{L}\neq\mathbf{NL}$$\mathbf{L}=\mathbf{NL}$$\mathbf{L}\neq\mathbf{NL}$$\mathbf{P}$$\mathbf{NP}$$\mathbf{L}$$\mathbf{NL}$$\mathbf{P}$$\mathbf{NP}$ lub odwrotnie.)

Znamy , gdzie równość wynika z twierdzenia Savitcha . Niedeterministyczna wersja twierdzenia o hierarchii przestrzeni mówi, że N L ≠ N P S P A C $\mathbf{L}\subseteq \mathbf{NL} \subseteq \mathbf{P} \subseteq \mathbf{NP} \subseteq \mathbf{PSPACE} = \mathbf{NPSPACE}$$\mathbf{NL}\neq \mathbf{NPSPACE}$więc wiemy, że co najmniej jedno z zestawów włączeń musi być ścisłe. Mamy trochę pomyśleć wszyscy są surowe ale nasza obecna wiedza nie wyklucza jakąkolwiek podzbiór z nich, o ile zawiera on co najmniej jedna spośród i P S P A C E .$\mathbf{NL}$$\mathbf{PSPACE}$