Na rzadkich kompletach i P vs L.

10

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 ”)NPP=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 ?PP=L

Michael Wehar
źródło

Odpowiedzi:

10

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ł .PP=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ł .NLNL=L

William Hoza
źródło
Łał! Dziękuję bardzo!! To jest świetne. :)
Michael Wehar