Dlaczego nie przyjąć jednolitej reprezentacji liczb w algorytmach numerycznych?

Pseudo-wielomianowy algorytm czasu jest algorytmem, który ma wielomianowy czas działania na wartości wejściowej (wielkość), ale wykładniczy czas działania na wielkości wejściowej (liczba bitów).

Na przykład sprawdzenie, czy liczba jest liczbą pierwszą, czy nie, wymaga przejścia przez liczby od 2 do i sprawdzenia, czy mod wynosi zero, czy nie. Jeśli mod zajmuje czas O (1), ogólna złożoność czasu wyniesie O (n).n - 1 n $n$$n-1$$n$ $i$

Ale jeśli pozwolimy być liczbą wymaganych bitów do zapisania danych wejściowych, to (binarny), więc a czas działania problemu wyniesie O ( ), który jest wykładniczy.x = log n n = 2 x 2 $x$$x = \log n$$n = 2^x$$2^x$

Moje pytanie brzmi: jeśli weźmiemy pod uwagę jedność reprezentacji danych wejściowych , to zawsze a następnie czas pseudo-wielomianowy będzie równy złożoności czasu wielomianowego. Dlaczego więc nigdy tego nie robimy?x = $n$$x=n$

Ponadto, ponieważ istnieje pseudo-wielomianowy algorytm czasu dla plecaka, przyjmując , plecak będzie wielomianem w wyniku P = NP$x=n$

Oznacza to, że plecak jednoargumentowy znajduje się w P. Nie oznacza to, że plecak (z liczbami zakodowanymi binarnie) znajduje się w P.

Plecak jest znany jako NP-zupełny. Jeśli pokazałeś, że plecak jest w P, oznaczałoby to, że P = NP.

Ale nie pokazałeś, że plecak znajduje się w P. Wykazałeś, że plecak jednoargumentowy znajduje się w P. Jednak wiadomo, że plecak jednoargumentowy nie jest NP-zupełny (w rzeczywistości standardowe podejrzenie jest takie, że nie jest NP-zupełny ). Dlatego umieszczenie jednoargumentowego plecaka w P nie oznacza, że ​​P = NP.

Więc na jakim problemie powinniśmy się bardziej przejmować, plecakiem czy pojedynczym plecakiem? Jeśli twoja motywacja opiera się na praktycznych kwestiach, odpowiedź będzie zależeć od wielkości liczb, dla których chcesz rozwiązać problem plecaka: jeśli są duże, to na pewno bardziej zależy ci na plecaku niż na pojedynczym plecaku. Jeśli twoja motywacja opiera się na kwestiach teoretycznych, to plecak jest prawdopodobnie bardziej interesujący, ponieważ pozwala nam na głębsze zrozumienie - pozwala nam odróżnić rozmiar od wielkości - podczas gdy plecak jednoargonowy uniemożliwia nam to rozróżnienie.

Aby odpowiedzieć na pytanie uzupełniające dotyczące algorytmu programowania dynamicznego dla problemu plecaka:

Tak, ten sam algorytm programowania dynamicznego można zastosować zarówno do plecaków, jak i do pojedynczego plecaka. Jego czas działania jest wielomianowy pod względem liczb, ale wykładniczy (nie wielomianowy) pod względem długości liczb, gdy jest zakodowany binarnie. Zatem jego czas działania jest wielomianowy w długości wejścia, gdy dane wejściowe są kodowane jako jednoargumentowe, ale nie jest wielomianowy w długości wejścia, gdy dane wejściowe są kodowane binarnie. Dlatego należy rozważyć ten algorytm programowania dynamicznego być algorytm wielomianowy czas jednoargumentowego plecaka, ale nie uważają, że jest to algorytm wielomianowy czas (binarny zakodowany) plecaka.

Przypomnijmy, że mówimy, że algorytm działa w czasie wielomianowym, jeśli jego czas działania jest co najwyżej jakimś wielomianem długości danych wejściowych, w bitach .

Dodałbym jedną małą rzecz do odpowiedzi DW:

Widziałem ludzi, którzy tak myślą, ponieważ jednoargumentowy plecak jest w P, dlatego możemy go użyć zamiast Knapsacka, które najlepsze obecne algorytmy mają czas wykładniczy.

Niech będzie wejście i i rozważyć algorytm programowania dynamicznego dla plecakowych oraz jednoargumentowego Knapsack. Czas działania obu z nich to . To ten sam czas działania. To znaczy, jeśli masz dane wejściowe, nie będzie miało znaczenia, czy użyjesz programowania dynamicznego dla jednoargumentowego plecaka, czy programowania dynamicznego dla plecaka. Obaj zajmą (mniej więcej tyle samo czasu) na rozwiązanie problemu. Teoretycznie wszędzie, gdzie używasz jednego, możesz także użyć drugiego. Musisz tylko przekonwertować liczby z jednych na binarne i odwrotnie.k O ( n k $W=\{w_1, \ldots, w_n\}$$k$$O(nk)$

Jaki jest więc sens definiowania złożoności algorytmów względem wielkości danych wejściowych? Dlaczego nie zawsze podawać je pod względem parametrów jako ?$O(nk)$

Jeśli zależy ci na problemie w izolacji, możesz to zrobić. W rzeczywistości tak często robią ludzie w algorytmach. Złożoność algorytmów graficznych jest często wyrażana w kategoriach liczby wierzchołków i liczby krawędzi, a nie wielkości łańcucha, który je koduje.

Ale dzieje się tak tylko wtedy, gdy mamy do czynienia z odosobnionym problemem. Nie jest to przydatne, gdy mamy do czynienia z problemami z różnego rodzaju danymi wejściowymi. W przypadku wykresów możemy mówić o czasie wykonywania wrt do liczby wierzchołków i krawędzi. W przypadku plecaka możemy porozmawiać o liczbie przedmiotów i wielkości plecaka. Ale co, jeśli chcemy porozmawiać o obu? Na przykład, gdy chcemy zmniejszyć liczbę problemów lub omówić klasę problemów, która obejmuje dowolne problemy, a nie tylko te z grafem jako danymi wejściowymi. Potrzebujemy uniwersalnego parametru wejść. Ogólnie rzecz biorąc, dane wejściowe to tylko ciąg znaków, to my interpretujemy ich symbole jako liczby jednostkowe, liczby binarne, wykresy itp. Aby opracować ogólną teorię złożoności algorytmu i problemów, potrzebny jest ogólny parametr danych wejściowych. Rozmiar danych wejściowych jest oczywistym wyborem i okazuje się na tyle solidny, że możemy na nim zbudować rozsądną teorię. To nie jedyna możliwość. Dla sztucznego możemy zbudować teorię opartą na$2$ do wielkości wejścia. Będzie dobrze działać.

Teraz decydujemy się na użycie rozmiaru jako naszego uniwersalnego parametru wejściowego, który zmusza nas do myślenia o kodowaniu obiektów w kategoriach łańcuchów. Są różne sposoby ich kodowania i mogą mieć różne rozmiary. (Sprawiają też, że różne rzeczy stają się łatwe / trudne.) Z punktu widzenia ogólnej teorii algorytmów ważne jest, czy kodujemy liczbę wejściową w jednostkowej, czy binarnej. Jeśli używamy jedności, a wielkość wynosi największa liczba, jaką otrzymamy, to . Jeśli używamy binarnego, może być tak duże jak . Więc kiedy mówimy o czasie wykonywania rozwiązywania problemów z plecakiem, gdzie rozmiar100 100 K 2 100 - 1 k k 2 100 - $k$$100$$100$$k$$2^{100}-1$$k$wynosi 100, otrzymujemy dwie bardzo różne sytuacje: w jednym przypadku dbamy tylko o dane wejściowe, w których wynosi co najwyżej 100. W drugim przypadku dbamy o dane wejściowe, które mogą być tak duże, jak .$k$$2^{100}-1$

Powiedzmy, że chcę sprawdzić, czy mogę zredukować SAT do plecaka w czasie wielomianowym. Powiedzmy, że formuła wejściowa dla SAT ma rozmiar . Wtedy będę mógł zbudować tylko wejście dla Knapsack która ma rozmiar wielomianu w . Powiedzmy, że to rozmiar danych wejściowych dla plecaka, który buduję. Jeśli użyję jedności, mogę jedynie ustawić na najwyżej . Jeśli używam binarnego, mogę ustawić tak duże, że . Okazuje się, że muszę ustawić dość duży, aby móc zredukować SAT do Knapsacka. Tak więc unary Knapsack nie będzie działał na redukcję SAT do niego. Jednak binarny plecak działałby. Będziemy mogli stworzyć instancję Knapsack ze znacznie większym$n$$n$$p(n)$$k$$p(n)$$k$$2^{p(n)}-1$$k$$k$ jeśli użyjemy binarnego.

Inny sposób myślenia na ten temat: Załóżmy, że masz czarne pudełko, które rozwiązuje jednoetapowy plecak, i drugie, które rozwiązuje plecakowy. Załóżmy, że masz czas na zapisanie bitowego wpisu dla czarnej skrzynki. Która z czarnych skrzynek ma większą moc? Oczywiście ten, który wykorzystuje kodowanie binarne. Możemy go użyć do rozwiązania problemów plecaka, które mają wykładniczo większy porównaniu z problemami, które może rozwiązać pojedyncza czarna skrzynka plecaka.$n$$k$

Krótko i prosto pokażę ci dlaczego.

Załóżmy, że masz algorytm faktoryzacji. Z wyjątkiem niewielkiej różnicy, że jedna akceptuje liczby całkowite do wprowadzania, a druga . Jak widać, oba fragmenty kodu są podobne.$Tally$

x = input integer

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

Zauważ, że powyższy algorytm jest wielomianem wartości liczbowej . Zajmie to liczby kroków w pętli. Ale jeśli chodzi o rozmiar bitowy, to w rzeczywistości .$x$$x$$O(2^n)$

Załóżmy, że dokonam niewielkiej zmiany w kodzie, który zajmie . Będzie to teraz czas zarówno w wartości, jak i długości wejścia .$Tally/Unary$$O(n)$$x$

x = input tallies

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

Reprezentacja wejściowa nie przyspiesza działania kodu. Mimo że drugi algorytm jest naprawdę wieloczasowy. Nie jest bardzo praktyczne w znalezieniu czynników dla RSA.