Na rzadkich kompletach i P vs L.

Twierdzenie Mahaneya mówi nam, że jeśli istnieje rzadki zestaw przy wielomianowych redukcjach wielokrotności jeden, to . (Patrz „ Rzadkie kompletne zestawy dla NP: Rozwiązanie przypuszczenia Bermana i Hartmanisa ”)$NP$$P = NP$

Czy znane są konsekwencje istnienia rzadkich kompletnych zestawów dla innych klas złożoności? W szczególności, jeśli w obszarze logarytmicznym występuje wiele rzadkich zestawów -komplementarnych, czy oznacza to, że ?$P$$P = L$

Tak, dokładnie to, co zasugerowałeś, jest prawdą: jeśli istnieje rzadki -kompletny zestaw pod redukcją przestrzeni dziennej wiele jeden, to . Zostało to przypuszczone przez Hartmanisa w 1978 roku i udowodnione przez Cai i Sivakumar w 1995 roku. Zobacz ten artykuł .$\mathbf{P}$$\mathbf{P} = \mathbf{L}$

Hartmanis również przypuszczał, że jeśli istnieje rzadki -kompletny zestaw w obszarze log-redukcje wiele jeden, to . Zostało to również udowodnione przez Cai i Sivakumar w 1997 r .; zobacz ten inny artykuł .$\mathbf{NL}$$\mathbf{NL} = \mathbf{L}$