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

15

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 inn1n 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 xxx=lognn=2x2x

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 = nnx=n

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

M ama D.
źródło
3
W rzeczywistości robimy to, po prostu niezbyt często. Z tych samych powodów zwykle nie mamy do czynienia z językami jednoargumentowymi, ale istnieje wiele interesujących wyników związanych z tymi bestiami. Zajrzałeś do tego?
André Souza Lemos
2
Tak, jeśli usuniesz różnicę między wielkością a wielkością, stracisz wszystkie koncepcje oparte na tej różnicy.
André Souza Lemos
7
Ponieważ wkłada demona w ładną sukienkę. Nie przyspiesza niczego, a jedynie „komplikuje czas działania”.
Raphael
4
@Drupalist Unary problem plecakowy faktycznie nie jest znany jako NP-zupełny, ponieważ normalne zmniejszenie problemu plecakowego zakłada, że ​​liczby są zapisywane w postaci binarnej. Jeśli spróbujesz wykonać standardową redukcję, ale zapiszesz liczby pojedynczo, redukcji nie można obliczyć w czasie wielomianowym. W rezultacie jednoargumentowy problem plecakowy rozwiązany w czasie wielomianowym nie oznaczałby, że P = NP.
templatetypedef
2
Możesz sprawdzić inne odpowiedzi oznaczone pseudo-wielomianem , w szczególności .
Raphael

Odpowiedzi:

17

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 .

DW
źródło
1
Dziękuję bardzo, nie wiedziałem, że klasa złożoności tego samego algorytmu może być różna. Dlaczego dynamiczne rozwiązanie programistyczne standardowego plecaka nie może być zastosowane do pojedynczego plecaka i doprowadziło do innej klasy złożoności? Mam problem ze zrozumieniem jednolitej wersji problemów.
M am D
@Drupalist, zredagowałem swoją odpowiedź, aby dodać dwa akapity na końcu, aby odpowiedzieć na to pytanie.
DW
Dziękuję bardzo, z tego, co rozumiem, różnica między wielkością wejściową a jej wielkością jest przyczyną rozróżnienia między wielomianem a pseudo-wielomianem, stosując jednostkową reprezentację starałem się wyeliminować tę różnicę, jeśli zapomnimy plecaka i wrócimy do liczb algorytmy, chciałbym wiedzieć, ustawiając jaka będzie interpretacja wielomianu i pseudo-wielomianu? Jeszcze raz dziękujęx=n
M am D
@Drupalist, nie jestem do końca pewien, co masz na myśli, ustawiając , więc nie jestem pewien, jak odpowiedzieć. W tym miejscu sugerowałbym, że najlepiej zadać nowe (samodzielne) pytanie (i zdefiniować wszystkie zmienne w tym pytaniu). Ta platforma nie jest zbyt dobra w przypadku pytań uzupełniających i zwrotnych: najlepszym sposobem, aby sobie z tym poradzić, jest zadanie nowego pytania, w oparciu o to, czego nauczyłeś się z odpowiedzi na to pytanie. x=n
DW
1
@NikosM. OK, rozumiem. Dziękujemy za opinię. Osobiście nie wierzę, że to stwierdzenie jest niepoprawne, więc zostawiam je bez zmian. (Moje rozumowanie: długość danych wejściowych zależy od wyboru reprezentacji, więc nie wierzę, że przeczy to temu, co napisałeś). Jednak jest całkiem możliwe, że moja perspektywa może być zbyt wąska lub że bardziej szczegółowe wyjaśnienie lub wyjaśnienie z inna perspektywa może wnieść wartość dodaną. Napisz dodatkową odpowiedź lub zasugeruj edycję, jeśli uważasz, że ten punkt może być jaśniejszy.
DW
6

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={w1,,wn}kO(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ą na2 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 - 1k100100k21001kwynosi 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 .k21001

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ększymnnp(n)kp(n)k2p(n)1kk 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.nk

Kaveh
źródło
Dziękuję bardzo, jeszcze jedno pytanie, konwertując dane wejściowe na jego jednoargumentową reprezentację, co stanie się z problemem ustalenia, czy liczba jest liczbą pierwszą, czy nie? Ten problem jest wielomianowy oparty na wielkości wejściowej, ale wykładniczy oparty na bitach wejściowych (jak wskazałem w pytaniu), czy ta konwersja poprawi coś?
M am D
@Drupalist, powiedzmy, że używamy prostego algorytmu, który przekracza liczby mniejsze niż aż znajdzie czynnik. Jego czas działania jest niezależny od od tego, czy kodujesz jako jednoargumentowy czy binarny. Jeśli masz liczbę 1024 bitów, np. , algorytm zajmie (z grubsza) niezależnie od tego, czy podasz jako jednoargumentowy czy jako dwójkowy. Dla konkretnego wejścia, na którym chcesz uruchomić algorytm, niewiele się zmieni, jeśli podasz go jako jednoargumentowy lub binarny. O ( n ) n b =nO(n)nb=210241210241210241
Kaveh
fajne wyjaśnienie, jednak spójrz na mój komentarz pod odpowiedzią DW, który jest związany z tym postem
Nikos M.
2

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 .xxO(2n)

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/UnaryO(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.

Travis Wells
źródło
Dobry przykład, dzięki
M am D