Jeśli problem X (problem decyzyjny) jest znany jako NP-Complete, a udowodniono, że ogranicza się do problemu Y, czy możesz powiedzieć, że problem Y jest NP-Complete?

Question

Jeśli problem X (problem decyzyjny) jest znany jako NP-Complete i udowodniono, że jest zredukowany do problemu Y w czasie wielomianowym, czy możesz powiedzieć, że problem Y jest NP-Complete?

Moja pierwsza myśl była, nie, problem Y musi być pokazany, że jest w NP. Ale po dalszych myślach, jeśli X jest zredukowany do Y, Y jest już uważany za NP-Complete. Teraz jestem po prostu zdezorientowany ... każda pomoc będzie doceniona.

Answer 1

argumentum za contrarium:

Jeśli X ∈ NP X ⇔ Y i Y ∉ NP to X ∉ NP.

Answer 2

Problem X - Niepewny
Problem Y - W NP

Aby udowodnić X jest w NP, można pokazać, że można śledzić kroki w celu zmniejszenia każdy problem w X do problemu w Y. Wtedy wiesz, że Problem X jest co najmniej tak trudny, jak odpowiadający mu problem Y.

Więc nie, trzeba zacząć od Y, a następnie zmniejszyć do X.

Answer 3

SAT może być rozwiązany w jednym wezwanie do wszystkich, ale to nie znaczy, że wszystko jest w NP.

Answer 4

Tak, zgadza się. Możesz zredukować swój problem w czasie wielomianu do dowolnego już znanego NP pełnego problemu, ale jest to uważane za bardzo trudne zadanie. Zamiast tego wybierasz już pełny problem NP i redukujesz go do swojego problemu, a także pokazujesz, że jest on w NP, wtedy twój problem będzie NP kompletny.

Answer 5

Jeszcze nie, trzeba będzie jeszcze kilka kroków

W celu udowodnienia, że ​​problem L jest NP-zupełny, musimy wykonać następujące kroki:

1. Udowodnij problem L należy do NP (czyli że podane rozwiązanie można zweryfikować go w czasie wielomianowym)
2. wybrać znany problem NP-zupełny L „
3. opisać algorytm F, który przekształca się w L” L
4. Pro ve, że algorytm jest poprawny (formalnie: x ∈ L”wtedy i tylko wtedy, gdy f (x) ∈ L)
5. Udowodnić, że f algo działa w czasie wielomianowym

Dotychczas trzeba krok 2,3, 4
Nadal trzeba pokazać, że redukcja jest wielomianem (krok 5).