Czy złożoność problemów silnie NP-trudnych lub -kompletnych zmienia się, gdy ich dane wejściowe są kodowane w sposób jednoznaczny?

12

Czy trudność silnie trudnego NP lub problemu NP-zupełnego (jak np. Zdefiniowano tutaj ) zmienia się, gdy jego wejście jest jednoargumentowe zamiast kodowane binarnie?

Jaką różnicę ma to, że wejście problemu silnie trudnego NP jest zakodowane w sposób jednoznaczny? Chodzi mi o to, że jeśli wezmę na przykład słabo NP-kompletny problem Knapsack, jest on NP-kompletny, gdy jest kodowany binarnie, ale można go rozwiązać w czasie wielomianowym przez programowanie dynamiczne, gdy kodowane jest jednoargumentowo. Może ma to jakieś implikacje dla twardości wyższych poziomów wielomianowej heirarchii czasowej?

Czy pojęcie silnie ...- trudne dotyczy także innych klas złożoności, np. Wyższych klas wielomianowej hierarchii czasu?

Wcześniej zadałem to pytanie na stackoverflow.com, ale wskazano, że tutaj jest bardziej odpowiednie.

complexity-theory time-complexity np-complete użytkownik2145167
źródło
Czy powinienem zadać to pytanie lepiej na cstheory.stackexchange.com ? Po prostu nie wiedziałem, że istnieje. Odpowiedzi tutaj nie idą w kierunku, na który liczyłem.
user2145167
Dlaczego oni nie Są one (o ile wiem) prawidłowe, więc może twoje pytanie nie jest tym, które chcesz zadać? Poza tym informatyka teoretyczna dotyczy pytań TCS na poziomie badawczym , czego z pewnością nie jest.
Raphael

Odpowiedzi:

4

NNlog⁡NF(N)F(size)F(2size)

vonbrand
źródło
3

Nie.

Jeśli zmienisz kodowanie wejścia, zmienisz formalną definicję problemu, co oznacza, że ​​jest to inny problem . Złożoność pierwotnego problemu nie zmienia się, z tego samego powodu, że wskazywanie na inne światło na niebie nie zmienia masy księżyca.

JeffE
źródło
2
PP1
2

Krótka odpowiedź brzmi: jeśli wejście jest zakodowane w sposób jednoargumentowy, to jest dłuższe . Jest wykładniczo dłuższy. Teraz algorytm działający w czasie wielomianowym w wielkości danych wejściowych ma „wystarczająco dużo czasu”, aby rozwiązać problem, tylko dlatego, że dane wejściowe są wykładniczo dłuższe niż w pierwotnym problemie.

Ran G.
źródło
1

Widząc przeszłość problemu sformułowania wskazanego w odpowiedzi JeffE, odpowiedź brzmi tak.

Rozważ problem z plecakiem . Ma algorytm pseudo-wielomianowy , to znaczy taki, w którym środowisko wykonawcze jest ograniczone przez wielomian w liczbie zakodowanej na wejściu. Ponieważ w jednostronnych wartościach kodowania odpowiadają długości, jest to algorytm wielomianowy dla wersji jednoargumentowej.

W rzeczywistości każdy słabo kompletny problem NP należy do tej kategorii.

Raphael
źródło
Pytanie poboczne, ale nigdy nie zrozumiałem - jak w ogóle „coś” zakodować? Nie potrzebujesz jakiegoś separatora?
user541686,
@ Mehrdad Tak i nie. Tak; symbole separacji zwykle nie są liczone w tym sensie, patrz także alfabet wejściowy vs. tutaj bierzemy pod uwagę tylko rozmiar alfabetu wejściowego. Nie; w zasadzie jedna liczba wystarcza do zakodowania krotek i policzalnych zestawów liczb, więc nie potrzebujesz symboli separacji. To oczywiście nie jest przydatne do „pracy” z takimi maszynami, ale uzasadnia to ignorowanie symboli separacji (i innych elementów sterujących).
Raphael
Hmm ... Nie jestem pewien, czy rozumiem twoją część „nie”; skąd wiedziałbyś, gdzie kończy się liczba, gdybyś nie miał separatora na końcu? Wydaje mi się to trochę jak logika kołowa: jeśli ignorujemy separatory, wówczas skutecznie pojawia się pytanie: „jeśli wymuszamy, aby dane wejściowe zajmowały wykładniczo więcej miejsca, czy to zmienia czas działania algorytmu wykładniczego w stosunku do wielkości wejściowej ? którego odpowiedź brzmi banalnie tak ... z definicji. Nie tyle zmienia kodowanie, ile sztucznie dodaje zbędne bity, gdy weźmie się pod uwagę separatory.
user541686,
@ Mehrdad Okay, myślałem tylko o oddzieleniu wielu liczb od siebie. W każdym razie potrzebujesz markerów końcowych lub. „puste” symbole na maszynach Turinga; którego nie możesz się pozbyć. Resztę możesz zakodować w jeden numer (oczywiście w czasie wykonywania).
Raphael