Mam wrażenie, że dla każdego problemu NP-zupełnego, dla nieskończenie wielu rozmiarów wejściowych , liczba wystąpień tak we wszystkich możliwych wejściach wielkości jest (przynajmniej) wykładnicza w n .
Czy to prawda? Czy można to udowodnić (prawdopodobnie tylko przy założeniu, że )? A może sztucznie możemy znaleźć problem, w którym dla wszystkich (wystarczająco dużych) liczba wystąpień tak jest co najwyżej wielomianowa w ?
Moje rozumowanie jest w gruncie rzeczy takie, że biorąc pod uwagę tak dla instancji 3-SAT, możemy zidentyfikować literał w każdej klauzuli, który sprawia, że jest to prawdą, i zastąpić inną zmienną w klauzuli inną zmienną, bez zmiany, czy jest zadowalająca. Ponieważ moglibyśmy to zrobić z każdą klauzulą, prowadzi to do wykładniczej liczby wystąpień tak. To samo dotyczy wielu innych problemów, takich jak ścieżka hamiltonowska: możemy dowolnie zmieniać krawędzie, które nie są na ścieżce. Rozsądnie rozumiem zatem, że skoro występuje redukowalność, gdzie w jakiś sposób trzeba zachować rozwiązania, musi ona dotyczyć wszystkich problemów z NP-zupełnością.
Wydaje się również, że dotyczy to prawdopodobnie NP-pośredniego problemu izomorfizmu grafów (gdzie możemy dowolnie zastosować te same zmiany do obu wykresów, jeśli znamy mapowanie). Zastanawiam się, czy dotyczy to również faktoryzacji liczb całkowitych.
źródło