Niedawno czytałem bardzo fajny artykuł Valianta i Vazirani, który pokazuje, że jeśli , to nie może być skutecznego algorytmu do rozwiązania SAT, nawet pod obietnicą, że jest albo niezadowalający, albo ma unikalne rozwiązanie. W ten sposób pokazując, że SAT nie dopuszcza wydajnego algorytmu nawet pod obietnicą istnienia co najwyżej jednego rozwiązania.
Dzięki oszczędnej redukcji (redukcji, która zachowuje liczbę rozwiązań) łatwo jest zauważyć, że większość problemów z NP-zupełnymi (mogłam wymyślić) również nie dopuszcza wydajnego algorytmu nawet pod obietnicą, że będzie co najmniej jedno rozwiązanie (chyba że ). Przykładami mogą być VERTEX-COVER, 3-SAT, MAX-CUT, 3D-MATCHING.
Dlatego zastanawiałem się, czy istnieje jakiś problem z całkowitą NP, o którym wiadomo, że dopuszcza algorytm wieloczasowy pod obietnicą wyjątkowości.