Jeśli P = NP, dlaczego

15

Najwyraźniej, jeśli , wszystkie języki w z wyjątkiem i byłyby -kompletne.P=NPPΣNP

Dlaczego w szczególności te dwa języki? Czy nie możemy zredukować do nich żadnego innego języka w , wysyłając je podczas przyjmowania lub odrzucania?P

David Faux
źródło

Odpowiedzi:

25

Ponieważ w nie ma żadnych ciągów , każda maszyna, która go oblicza, zawsze odrzuca, więc nie możemy odwzorować wystąpienia innych problemów na tak. Podobnie w przypadku Σ nie ma nic do mapowania Bez instancji.

Luke Mathieson
źródło
4

Potrzebny jest wielomian redukcję od problemu A do problemu B , jeśli chcesz, aby udowodnić, że B jest „twardszy” niż A . Zbudować wielomianu redukcji, przekształcając każdy przypadek x z A do wystąpienia f(x) w B tak, że xA IFF f(x)B .

Funkcja musi i może być wielomianowa. Jeżeli P = N P i jest problemem, np, po czym f sam może rozwiązać problem A problemu i osadzenia każdy x do jakiegoś elementu y do B i każdy x do jakiegoś pierwiastka Z , które nie są w B .fP=NPAfAxAybxZAzB

Jeśli jest albo lub wtedy lub nie istnieje poza rozumowanie powyżej wynika, że jest twardszy niż .BΣyzBZA

jmad
źródło
3

Tylko uwaga: poprzednie odpowiedzi są w porządku, jednak nie jesteś zbyt daleki od prawidłowej trywialnej redukcji:

jeśli to każdy można Karp zredukować do języka (wystarczy mapować w czasie wielomianowym co na 1, co do 0), co jest trywialnie rzadkim językiemP=NPLNP{1}xLxL.

Odwrotny kierunek: „jeśli kompletny język daje się Karpowi sprowadzić do rzadkiego zbioru, wówczas ” jest z pewnością bardziej interesujący i jest znany jako twierdzenie Mahaneya :NPP=NP

Niech być stała i być ustawione tak, że dla wszystkich , ma co najwyżej ciągi o długości . Jeśli jest -kompletny, to .cAnAncnANPP=NP

Vor
źródło