Kekerasan dan arah pengurangan

Katakanlah kita tahu bahwa masalah A itu sulit, maka kita mengurangi A menjadi masalah yang tidak diketahui B untuk membuktikan B juga sulit.

Sebagai contoh: kita tahu pewarnaan 3 itu sulit. Lalu kami mengurangi 3-pewarnaan menjadi 4-pewarnaan. Dengan menggabungkan salah satu warna dalam 3-pewarnaan Anda memiliki 4-pewarnaan, ergo 4-pewarnaan itu sulit.

Begitulah caranya. Tapi mengapa ini bukti bahwa pewarnaan 4 itu sulit? Apakah Anda dapat menggunakan solusi untuk masalah 4-warna untuk menyelesaikan masalah 3-warna? Jika ya, bagaimana caranya? Jika tidak, mengapa itu bukti yang sah?

Bonus q: Haruskah pengurangan polinom dapat berjalan dalam dua arah?

Sunting: jika Anda dapat menjelaskan mengapa demikian dengan contoh, Anda akan melakukan bantuan internet. Saya tidak dapat menemukan ini dijelaskan secara konkret di mana pun.

Penurunan dari masalah ke masalah lain adalah transformasi dari setiap contoh sebuah dari menjadi contoh dari , sehinggaB f A f ( a ) $A$$B$$f$$a$$A$$f(a)$$B$

Jika adalah transformasi yang menjaga kompleksitas yang Anda minati (mis. adalah transformasi polinomial jika Anda mempertimbangkan -kekerasan) maka keberadaan algoritma penyelesaian menyiratkan adanya penyelesaian algoritma : cukup menjalankan , lalu .f N P A B B A f A$f$$f$$\mathsf{NP}$$\mathcal A_B$$B$$A$$f$$\mathcal A_B$

Oleh karena itu keberadaan pengurangan tersebut dari ke berarti bahwa tidak lebih mudah dari . Tidak perlu memiliki pengurangan dengan cara lain.B B $A$$B$$B$$A$

Misalnya, untuk pewarnaan grafik. Anda dapat mengurangi 3-pewarnaan menjadi 4-pewarnaan tetapi tidak dengan segera. Jika Anda mengambil grafik dan Anda memilih maka Anda akan mendapatkan tetapi Anda tidak memiliki tentu saja. Kesimpulannya adalah bahwa kesetaraan tidak dihormati, sehingga adalah bukan pengurangan.f ( G ) = G x ∈ 3 C O L ⇒ f ( x ) ∈ 4 C O L f ( x ) ∈ 4 C O L ⇒ x ∈ 3 C O L ( E ) $G$$f(G)=G$$x∈3\mathsf{COL}$ $⇒$ $f(x)∈4\mathsf{COL}$$f(x)∈4\mathsf{COL}$ $⇒$ $x∈3\mathsf{COL}$$(E)$$f$

Anda dapat membuat pengurangan yang benar dari ke tetapi sedikit lebih rumit: untuk grafik apa saja , misalkan berupa grafik diperluas dengan simpul lain yaitu dihubungkan dengan tepi ke setiap simpul lainnya.3 C O L 4 C O L G f ( G ) G $f$$3\mathsf{COL}$$4\mathsf{COL}$$G$$f(G)$$G$$u$

• Transformasi adalah pelestarian kompleksitas (jumlahnya banyak, di sini);
• jika dalam maka dalam : cukup gunakan warna keempat untuk ;$G$$3\mathsf{COL}$$f(G)$$4\mathsf{COL}$$u$
• Jika dalam maka Anda dapat membuktikan bahwa semua node kecuali memiliki warna yang bukan , maka berada dalam .$f(G)$$4\mathsf{COL}$$u$$u$$G$$3\mathsf{COL}$

Itu membuktikan bahwa adalah pengurangan dan bahwa lebih sulit daripada . Anda dapat membuktikan dengan cara yang sama bahwa lebih sulit daripada untuk apa pun , bukti yang menarik adalah kenyataan bahwa lebih sulit daripada .4 C O L 3 C O L n C O L m C O L n ≥ m 3 C O L n C O $f$$4\mathsf{COL}$$3\mathsf{COL}$$n\mathsf{COL}$$m\mathsf{COL}$$n≥m$$3\mathsf{COL}$$n\mathsf{COL}$