Jeśli P = NP, dlaczego

Najwyraźniej, jeśli , wszystkie języki w z wyjątkiem i byłyby -kompletne.${\sf P}={\sf NP}$${\sf P}$$\emptyset$$\Sigma^*$${\sf 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?${\sf P}$

Ponieważ w nie ma żadnych ciągów $\emptyset$, 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 $\Sigma^{\ast}$ nie ma nic do mapowania Bez instancji.

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 $x∈A$ 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 .$f$$\mathsf{P}=\mathsf{NP}$$A$$f$$A$$x∈A$$y$$B$$x\notin A$$z$$B$

Jeśli jest albo ∅ lub wtedy lub nie istnieje poza rozumowanie powyżej wynika, że jest twardszy niż .$B$$∅$$Σ^*$$y$$z$$B$$A$

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ęzykiem$\sf{P} = \sf{NP}$$L \in \sf{NP}$$\{1\}$$x \in L$$x \notin L$

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 :$\sf{NP}$$\sf{P}=\sf{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 .$c$$A$$n$$A$$n^c$$n$$A$$\sf{NP}$$\sf{P}=\sf{NP}$