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 ”)
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 ?