1
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 …