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

4

$N$ $N$ $\log N$ $F(N)$ $F(\text{size})$ $F(2^{\text{size}})$

— 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

P

$P$

P_{1}

$P_1$

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