1
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 .nnnnnnnnn Czy to prawda? Czy można to udowodnić (prawdopodobnie tylko przy założeniu, że P.≠ N.P.P.≠N.P.P\neq NP )? A może sztucznie możemy znaleźć problem, w …