Zmniejszenie problemu faktoryzacji liczb całkowitych do problemu NP-Complete

17

Próbuję zrozumieć związek między NP-Intermediate a NP-Complete. Wiem, że jeśli P! = NP na podstawie twierdzenia Ladnera, istnieje klasa języków w NP, ale nie w P lub w NP-Complete. Każdy problem w NP można zredukować do problemu NP-Complete, jednak nie widziałem żadnych przykładów zmniejszania podejrzewanego problemu NPI (takiego jak rozkład liczb całkowitych) na problem NP-Complete. Czy ktoś wie o jakimkolwiek przykładzie tej lub innej redukcji NPI-> NPC?

np-complete reductions factoring Nathan Jordan
źródło
4
Dzięki definicji kompletności NP każdy problem w NP można zredukować do dowolnego problemu z NP-kompletnością. W szczególności twierdzenie Cooka pokazuje, że SAT jest NP-zupełny, a zatem daje „wyraźną” taką redukcję.
Yuval Filmus,
1
@YuvalFilmus Rozumiem, że istnieje formalizacja, że ​​taka metoda istnieje, ale szukałem bardziej konkretnego podejścia algorytmicznego podobnego do, powiedzmy, zmniejszenia problemu cyklu Hamiltonian do problemu Traveling Salesman. W którym możesz ustawić wszystkie grubości krawędzi na 1 i uruchomić TSP na wykresie i sprawdzić, czy przebyta odległość jest większa niż | E |. Coś takiego, jak sądzę.
Nathan Jordan,

Odpowiedzi:

11

Na przykład, istnieje klasyczna redukcja faktoringu do SAT, która jest również źródłem domniemanych „twardych” instancji SAT. Zasadniczo używa się pomysłów EE na binarne mnożenie zakodowane w obwodzie SAT. Pomyśl o mnożeniu binarnym jako o dodaniu szeregu mnożników przesuniętych w lewo, każdy „zamaskowany” (ANDed) przez bity mnożnika. Dodawanie można wykonać za pomocą binarnego obwodu dodawania, który jest serią pełnych sumatorów.

Utalentowany student może zbudować ten algorytm. Nie wiem, gdzie po raz pierwszy zaproponowano lub wdrożono w literaturze. Chciałbym usłyszeć wszelkie referencje.

Zobacz np. Satisfy This: Próba rozwiązania Prime Factorization za pomocą Solverisfilver Solvers autorstwa Stefana Schoenmackersa i Anny Cavender, która szczegółowo to opisuje. Również wyzwanie SAT DIMACS, które rozpoczęło się pod koniec lat 90., zawierało przypadki faktoringu wygenerowane przez niektórych badaczy, ale być może algorytm nie został osobno spisany w pracy w tamtym okresie.

vzn
źródło
1
fyi papierowy link jest teraz zabroniony 403
dniu
2
W odniesieniu do drugiego akapitu: twierdzenie Cooka pokazuje, że każdy problem w NP można zredukować do SAT.
Yuval Filmus,
1
prawda, dowód Cooka jest ogólnym teoretycznym dowodem na istnienie i istnieje więcej bezpośrednich / specjalistycznych konwersji / algorytmów często konstruowanych między NP całkowitymi problemami (zwykle z lepszym „narzutem”). odnosił się do tego ostatniego.
vzn
11

Żeby być absolutnie jasnym, faktoryzacja liczb całkowitych nie jest znana jako pośrednia NP, po prostu podejrzewa się, że opiera się na braku algorytmu potwierdzenia NP lub algorytmu czasu wielomianowego (pomimo wielu prac włożonych w oba). Nie znam żadnego naturalnego problemu (tj. Nie skonstruowanego przez Ladnera na dowód), który jest zdecydowanie pośredni NP, jeśli P i NP są różne.

Ok, po tym wyłączeniu odpowiedzialności, Graph Isomorphism jest kolejnym prawdopodobnym kandydatem na naturalny problem pośredni NP. Jest prosta redukcja czasu wielomianowego do izomorfizmu subgrafu - po prostu pozostaw te same wykresy! Izomorfizm grafów jest szczególnym przypadkiem izomorfizmu subgraficznego, w którym oba wykresy mają ten sam rozmiar. Ostatnim akcentem jest to, że izomorfizm subgrafu jest NP-kompletny.

Oprócz tego zawsze istnieje niezbyt pouczająca redukcja obiecana przez twierdzenie Cooka-Levina , wiemy, że każdy problem pośredni NP ma jakąś niedeterministyczną maszynę Turinga o wielomianowym czasie, i możemy ją przekonwertować na wystąpienie SAT (wystarczy zbudować TM!).

Luke Mathieson
źródło