Czy naprawdę można wykazać silną twardość NP za pomocą zwykłych redukcji czasu politytime?

17

Niedawno przeczytałem dowód, który miał wykazać, że problem był silnie NP-trudny, po prostu redukując go (w czasie wielomianowym) z problemu silnie NP-trudnego. To nie miało dla mnie żadnego sensu. Pomyślałbym, że musisz pokazać, że wszelkie liczby użyte w redukcji i przypadki problemu, do którego redukujesz, są wielomianowo ograniczone w wielkości problemu.

Potem zobaczyłem, że Wikipedia podała takie same ogólne instrukcje dla tego rodzaju dowodu, ale tak naprawdę nie byłem przekonany, dopóki nie zobaczyłem, że Garey i Johnson mówią w zasadzie to samo. Mówiąc konkretnie, mówią: „Jeśli jest twarde NP w silnym znaczeniu i istnieje pseudo-wielomianowa transformacja z na , wtedy $\Pi$ $\Pi$ $\Pi'$ $\Pi'$ jest NP-twarde w silnym tego słowa znaczeniu” i „Uwaga: z definicji algorytm wielomianowy jest również algorytmem pseudo-wielomianowym. ”

Oczywiście wierzę w to Garey & Johnson - po prostu nie rozumiem, jak to może być poprawne, z czym chciałbym trochę pomóc. Oto moje (prawdopodobnie błędne) uzasadnienie…

Występują problemy z silnym NP-zupełnym, a wszystkie te (z definicji) są silnie NP-trudne, a także NP-pełne. Każdy problem NP-zupełny może (z definicji) zostać zredukowany do dowolnego innego w czasie wielomianowym (a zatem pseudopolinomalnym). Biorąc pod uwagę stwierdzenia Garey & Johnson, wydaje mi się, że każdy problem NP-zupełny jest silnie NP-zupełny, a zatem każdy problem NP-trudny jest silnie NP-trudny. To oczywiście sprawia, że koncepcja dużej twardości NP nie ma znaczenia… więc czego mi brakuje?

Edytuj / aktualizuj (na podstawie odpowiedzi Tsuyoshi Ito):

Wymaganie (d) z definicji (pseudo) wielomianowej transformacji Gareya i Johnsona (rodzaj redukcji potrzebnej do nadania twardości NP w silnym tego słowa znaczeniu) jest to, że największą wartością liczbową w powstałym przypadku jest ograniczenie wielomianowe, jako funkcja rozmiaru problemu i maksymalnej wartości liczbowej oryginału. To oczywiście oznacza, że jeśli pierwotny problem jest NP-trudny w silnym znaczeniu (to znaczy, nawet jeśli jego wielkości liczbowe są wielomianowo ograniczone w rozmiarze problemu), będzie to również dotyczyć problemu, do którego redukujesz. To nie muszą być w przypadku zwykłej redukcji polytime (czyli jeden bez tego dodatkowego wymogu).

cc.complexity-theory np-hardness reductions

— Magnus Lie Hetland
źródło

Świetny! Moja matematyka TA zrobiła to wczoraj i uważałem to za podejrzane. Teraz mogę mu dać link.

— Raphael

14

Zgodnie z terminologią zawartą w pracy Gareya i Johnsona transformacje wielomianowe nie zawsze są transformacjami pseudo-wielomianowymi, ponieważ mogą naruszać pozycję (d) w definicji 4.

— Tsuyoshi Ito
źródło

1

Zgadza się - więc algorytm wielomianowy jest koniecznie pseudopolomiczny, ale redukcja wielomianu niekoniecznie jest tym, co G&J nazywa transformacją pseudopolomiczną. W rzeczywistości ich element (d) jest dokładnie tym, co moim zdaniem brakowało (tj. Pewne ograniczenie wielkości liczb). Dzięki.

— Magnus Lie Hetland

9

Aby rozwinąć odpowiedź Tsuyoshi:

W kontekście Garey i Johnsona rozważ przemianę ze PARTYCJI (s. 47, s. 3.1) na HARMONOGRAM MULTIPROCESORA (s. 65, s. 3.2.1, pozycja (7)).

$D=\frac{1}{2}\sum_{a\in A}l(a)$ $l(a)$ $q_2$ $\forall I \in D_{\Pi}$ $[f(I)] \le q_2$ $[I],$ $[I])$ (tj. pozycja (d) w definicji transformacji pseudo-wielomianowej).

$l(a)$ $l(a)$ $|A|$

Możesz przeczytać Wikipedię na podobny temat . Na przykład mamy dynamiczny algorytm wielomianowy oparty na programowaniu dla problemu NP-zupełnego KNAPSACK - przynajmniej tak długo, jak długo liczby są wystarczająco małe. Gdy liczby stają się zbyt duże, ten algorytm „czasu wielomianowego” wyświetli „zachowanie wykładnicze”. (G&J, s. 91, pkt 4.2)

— Daniel Apon
źródło