Twierdzenie Mahaneya
Twierdzenie Mahaneya jest twierdzeniem z teorii złożoności obliczeniowej udowodnionym przez Stephena Mahaneya, które stwierdza, że jeśli jakikolwiek rzadki język jest NP-zupełny , to P = NP. Ponadto, jeśli jakikolwiek rzadki język jest NP-zupełny w odniesieniu do redukcji Turinga , to hierarchia czasu wielomianowego zapada się do . .
Argument Mahaneya w rzeczywistości nie wymaga, aby język rzadki był w NP, więc istnieje rzadki zestaw NP-trudny wtedy i tylko wtedy, gdy P = NP. Dzieje się tak, ponieważ istnienie rzadkiego zbioru NP-trudnego implikuje istnienie rzadkiego zbioru NP-zupełnego.