Wszystkie problemy NP redukują się do problemów NP-zupełnych: w jaki sposób problemy NP nie mogą być NP-zupełne?

10

Moja książka to stwierdza

  • Jeśli problem decyzyjny B występuje w P, a A zmniejsza się do B, to problem decyzyjny A występuje w P.
  • Problem decyzyjny B jest NP-kompletny, jeśli B występuje w NP, a dla każdego problemu w A w NP A zmniejsza się do B.
  • Problem decyzyjny C jest NP-kompletny, jeśli C jest w NP, a dla niektórych NP-kompletnych problemów B, B zmniejsza się do C.

Więc moje pytania są

  1. Jeśli B lub C jest w NP-zupełny, a wszystkie problemy w NP redukują się do problemu NP-zupełnego, stosując pierwszą zasadę, w jaki sposób jakikolwiek problem NP nie może być NP całkowity?
  2. Jeśli A zmniejsza się do B, to czy B redukuje się do A?
complexity-theory np-complete decision-problem rubiksibuc
źródło
2
Interesujący fakt związany z twoim numerem 1: Jeśli P nie jest równe NP, wiemy, że muszą istnieć problemy NP, które nie są NP-zupełne (nazywa się to twierdzeniem Ladnera. Patrz NP Pośredni ). Dziwne jest to, że nie jesteśmy pewni żadnych typowych problemów obliczeniowych pasujących do tej kategorii. Problem zastosowany w twierdzeniu Ladnera jest sztucznie skonstruowany w celu udowodnienia twierdzenia, ale jest praktycznie nieistotny.
Lucas Cook
4
@Lucas, faktoring i GraphIso są Przypuszcza się NPI również zobaczyć to .
Kaveh
@Kaveh: Ładna lista kandydatów NPI, dzięki! Aby wyjaśnić, mówiłem, że nie jesteśmy „pewni” naturalnego problemu NPI z taką samą pewnością jak problemy Ladnera. To znaczy, jeśli , jedynymi znanymi niektórymi problemami NPI są sztuczne związane z hierarchią Ladnera. P≠NP
Lucas Cook

Odpowiedzi:

13

Jeśli A zmniejsza się do B, to czy B redukuje się do A?

Nie. Dla naprawdę wymyślonego przykładu każdy możliwy problem obliczalny A można zredukować do problemu zatrzymania: wystarczy przekazać jako dane wejściowe algorytm, który rozwiązuje problem A, ale z while(true)tikiem na końcu po prawdziwym lub fałszywym przypadku. Wiemy jednak, że problem zatrzymania nie jest obliczalny, więc nie można go sprowadzić do żadnego takiego algorytmu A.

Podstawową ideą jest to, że jeśli nastąpi redukcja z A do B, możesz dowiedzieć się, że B jest co najmniej tak samo trudny do rozwiązania, a A i wymaga algorytmu, który jest co najmniej tak samo wydajny.

Jeśli więc problem A sprowadza się do łatwego problemu B, możemy wywnioskować, że A jest łatwy (ponieważ redukcja daje nam skuteczny algorytm), a jeśli trudny problem A zredukowany do problemu B, możemy wywnioskować, że B jest również trudny ( ponieważ gdyby B było łatwe, A również musiałoby być łatwe). Jednak nadal istnieje możliwość niemądrej redukcji z łatwego problemu na trudny, ale w tym przypadku nie możemy wyciągać żadnych wniosków.

hugomg
źródło
8

Jeśli B lub C jest w NP Complete, a wszystkie problemy w NP redukują się do problemu NP Complete, stosując pierwszą zasadę, w jaki sposób jakikolwiek problem NP nie może być NP całkowity?

Pierwsza zasada dotyczy problemów w P. Nie ma to nic wspólnego z kompletnością NP. Jeśli problem A jest NP Complete, a problem B zmniejsza się do A, nie oznacza to, że B jest NP Complete.

Jeśli A redukuje się do B, to czy B redukuje się do A?

Nie ogólnie nie.

sepp2k
źródło
„Nie ogólnie nie.”, Dlaczego? Trochę wyjaśnienia może być również przydatne dla początkujących. Należy również wyjaśnić swoją pierwszą odpowiedź.
nbro
-1

Mam tylko podstawowe pojęcie dotyczące problemów NPC i NP. Ale wszystko, co chcę skomentować, dotyczy „Jeśli A jest zredukowane do B, to B jest zredukowane do A?”

Wystarczy rozważyć zestaw A zawierający {2,3,4,5} elementów i zestaw B zawierający {3,4}. Zatem A można zredukować do B. Ale B nie można zredukować do A. Zamiast tego B można rozszerzyć do A, jeśli B zyska {2,5} elementów.

Ale jeśli A i B mają to samo. następnie A można zredukować do B lub B można zredukować do A.

Naveen CS
źródło
To wcale nie jest właściwy pomysł redukcji. Redukcja nie polega na tym, że zestawy zyskują lub tracą elementy. Chodzi raczej o to, by móc przekonwertować wystąpienie jednego problemu na inny za pomocą maszyny / algorytmu Turinga.
jmite
Ok. Tak więc, jeśli jakikolwiek problem zostanie zredukowany do innego przy użyciu dowolnego algorytmu, nie będzie możliwe odzyskanie problemu ze zmniejszonej wydajności przy użyciu tego samego algorytmu ponownie.
Naveen CS
1
Nie jestem do końca pewien, co masz na myśli, ale myślę, że nie jest to możliwe. Jeśli się nie mylę, te redukcje mogą być wiele do jednego. A zmniejsza się do B, jeśli wielomianowa liczba wywołań do rozwiązania podprogramu B umożliwia rozwiązanie A w czasie wielomianowym. Różne instancje A mogą wywoływać wywołanie tej samej instancji B.
jmite
2
Pytanie dotyczy problemów decyzyjnych, a nie zbiorów. Jak warto patrzeć na zestawy? Używanie słowa „zredukowany” w celu oznaczenia, że ​​zestaw jest nadzbiorem innego, nie jest nawet powszechną terminologią.
Gilles 'SO - przestań być zły'