NP-Kompletne problemy, które dopuszczają wydajny algorytm pod obietnicą unikalnego rozwiązania

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.$\mathbf{NP \neq RP}$

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.$\mathbf{NP = RP}$

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.

Nie jest znany żaden problem związany z NP-całkowitym przyjęciem algorytmu czasu wielomianowego z obietnicą wyjątkowości. Twierdzenie Valiant i Vazirani dotyczy każdego znanego naturalnego problemu NP-zupełnego.

$NP$