NP-zupełny problem z wielomianową liczbą tak-wystąpień?

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 .$n$$n$$n$

Czy to prawda? Czy można to udowodnić (prawdopodobnie tylko przy założeniu, że $P\neq NP$ )? A może sztucznie możemy znaleźć problem, w którym dla wszystkich (wystarczająco dużych) $n$ liczba wystąpień tak jest co najwyżej wielomianowa w $n$ ?

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.

Język z wielomianowo wieloma wystąpieniami tak nazywany jest rzadkim . Twierdzenie Mahaneya stwierdza, że ​​jeśli dowolny język NP-zupełny jest rzadki, to P = NP. Ponieważ większość ludzi spodziewa się, że P $\ne$ NP, wydaje się mało prawdopodobne, aby istniał język NP-zupełny z wielomianowo wieloma tak.

Osobnym pytaniem jest, czy liczba wystąpień tak jest wykładnicza. (Można sobie wyobrazić, że liczba przypadków tak może być większa niż wielomianowa, ale mniej wykładnicza). Hipoteza Bermana-Hartmanisa jest tutaj istotna; oznacza to, że wszystkie problemy NP-zupełne mają wykładniczo wiele przypadków tak. Przypuszczenie pozostaje otwartym problemem.