Jika P = NP, mengapa

Rupanya, jika ${\sf P}={\sf NP}$ , semua bahasa dalam ${\sf P}$ kecuali $\emptyset$ dan $\Sigma^*$ akan menjadi ${\sf NP}$ -lengkap.

Mengapa dua bahasa ini khususnya? Tidak bisakah kita mengurangi bahasa lain dalam ${\sf P}$ ke mereka dengan mengeluarkannya saat menerima atau tidak menerima?

Karena tidak ada string dalam , mesin apa pun yang menghitungnya selalu menolak, jadi kami tidak bisa memetakan Ya-contoh masalah lain untuk apa pun. Demikian pula untuk Σ ∗ tidak ada yang bisa dipetakan untuk instance-no.$\emptyset$$\Sigma^{\ast}$

Anda perlu pengurangan jumlahnya banyak dari masalah ke masalah B jika Anda ingin membuktikan bahwa B adalah "sulit" dari A . Kami membangun pengurangan jumlahnya banyak dengan mengubah setiap contoh x dari A ke sebuah contoh f ( x ) dari B sehingga x ∈ A jika dan hanya jika f ( x ) ∈ B .$A$$B$$B$$A$$x$$A$$f(x)$$B$$x∈A$$f(x)∈B$

Fungsi harus dan bisa polinomial. Jika P = N P dan A merupakan masalah NP, maka f dapat sendiri memecahkan masalah Sebuah masalah dan embed setiap x ∈ A ke dalam beberapa elemen y dari B dan setiap x ∉ A ke dalam beberapa elemen z yang tidak di B .$f$$\mathsf{P}=\mathsf{NP}$$A$$f$$A$$x∈A$$y$$B$$x\notin A$$z$$B$

Jika adalah salah ∅ atau Σ * kemudian y atau z tidak bisa ada, jika tidak penalaran di atas menunjukkan bahwa B lebih sulit daripada A .$B$$∅$$Σ^*$$y$$z$$B$$A$

Hanya sebuah catatan: jawaban sebelumnya ok, namun Anda tidak terlalu jauh dari pengurangan sepele yang benar:

jika maka setiap L ∈ N P adalah Karp dapat direduksi ke bahasa { 1 } (hanya peta dalam waktu polinomial setiap x ∈ L ke 1, setiap x ∉ L ke 0), yang biasanya merupakan bahasa yang jarang$\sf{P} = \sf{NP}$$L \in \sf{NP}$$\{1\}$$x \in L$$x \notin L$

Arah sebaliknya: "jika bahasa lengkap Karp direduksi untuk satu set jarang kemudian P = N P " tentu lebih menarik dan dikenal sebagai teorema Mahaney ini :$\sf{NP}$$\sf{P}=\sf{NP}$

Biarkan menjadi konstanta dan A diatur sedemikian rupa sehingga untuk semua n , A memiliki paling banyak n c string panjang n . Jika A adalah N P -Lengkap maka P = N P .$c$$A$$n$$A$$n^c$$n$$A$$\sf{NP}$$\sf{P}=\sf{NP}$