Czy są znane algorytmy, które poprawnie wypisują odpowiedź „tak” dla problemu NP-complete bez pośredniego generowania certyfikatu?
Rozumiem, że łatwo jest przekształcić wyrocznię spełniającą w znajdującą satysfakcjonujące zadanie: po prostu iteruj po zmiennych, za każdym razem pytając wyrocznię spełniającą o rozwiązanie związku tej zmiennej z pierwotnym problemem.
Ale czy takie opakowanie byłoby kiedyś przydatne? Czy wszystkie satelitarne solwery przeszukują przestrzeń możliwych zadań?
A może istnieją jakieś rodzaje problemów z NP-zupełnością (podróżny sprzedawca, suma podzbiorów itp.), W których solver może, powiedzmy, wykorzystać twierdzenie matematyczne, aby udowodnić, że rozwiązanie musi istnieć? Jak robienie dowodu przez sprzeczność?
źródło