Czy istnieje znany, wyraźny przykład algorytmu o takiej właściwości, że jeśli to ten algorytm nie działa w czasie wielomianowym, a jeśli to działa w czasie wielomianowym?
ds.algorithms
np
p-vs-np
użytkownik2925716
źródło
źródło
Odpowiedzi:
Jeśli założysz, że można udowodnić w PA (lub ZFC), trywialny przykład jest następujący:P=?NP
Kolejny - mniej trywialny - przykład, który nie opiera się na żadnym założeniu, jest następujący:
Jeśli algorytm prędzej czy później - przypuśćmy, że na wejściu - znajdzie indeks wielomianowego czasu maszyny Turinga (lub jego wersji wyściełanej)P=NP x0 MSAT która rozwiązuje SAT w O ( | x || M.S.A T.|) i dla wszystkich danych wejściowych większych niż x0 będzie nadal symulować i zatrzymywać się w czasie wielomianowym (zwróć uwagę, że krok 2 można również sprawdzić w czasie wielomianowym). Innymi słowy, jeśli P.= NP. algorytm rozwiązuje SAT w czasie wielomianowym we wszystkich przypadkach oprócz skończonej liczby instancji.
JeśliP.≠ N.P. algorytm działa w czasie wykładniczym.
źródło