SETENGAH CLIQUE - NP Lengkap Masalah

Mari saya mulai dengan mencatat bahwa ini adalah masalah pekerjaan rumah, tolong berikan hanya saran dan pengamatan terkait, JANGAN JAWABAN LANGSUNG . Dengan itu, inilah masalah yang saya lihat:

Biarkan HALF-CLIQUE = { | adalah grafik tak berarah yang memiliki subgraph lengkap dengan setidaknya node, di mana n adalah jumlah node dalam }. Tunjukkan bahwa SETENGAH-CLIQUE adalah NP-lengkap.$\langle G \rangle$$G$$n/2$$G$

Saya juga tahu yang berikut ini:

• Dalam hal masalah ini , klik , didefinisikan sebagai subgraf tak berarah dari grafik input, di mana setiap dua node dihubungkan oleh sebuah edge. Sebuah -clique adalah kelompok yang berisi node.$k$$k$
• Menurut buku teks kami, " Pengantar Teori Komputasi " Michael Sipser , hal 268, bahwa masalahnya CLIQUE = { | adalah grafik tidak terarah dengan -clique} dalam NP$\langle G,k\rangle$$G$$k$
• Selanjutnya, menurut sumber yang sama (pada halaman 283) catat bahwa CLIQUE adalah dalam NP-Complpete (dengan demikian juga jelas dalam NP).

Saya pikir saya memiliki inti jawaban di sini, namun saya dapat menggunakan beberapa indikasi tentang apa yang salah dengan itu atau hal-hal terkait yang mungkin relevan dengan jawaban . Ini adalah ide umum yang saya miliki sejauh ini,

Ok, pertama saya perhatikan bahwa sertifikat hanya akan menjadi SETENGAH-QLIQUE dari . Sekarang nampaknya apa yang perlu saya lakukan adalah membuat verifier yang merupakan pengurangan waktu polinomial dari CLIQUE (yang kita tahu NP-Complete) ke HALF-CLIQUE. Ide saya adalah bahwa ini akan dilakukan dengan membuat mesin Turing yang menjalankan verifikasi mesin turing dalam buku untuk CLIQUE dengan kendala tambahan untuk HALF-CLIQUE.$\text{size} \geq n/2$

Ini kedengarannya benar bagi saya, tetapi saya belum benar-benar percaya pada subjek ini. Sekali lagi, saya ingin mengingatkan semua orang bahwa ini adalah MASALAH RUMAH TANGGA jadi tolong coba untuk menghindari menjawab pertanyaan. Bimbingan apa pun yang kurang dari ini akan sangat disambut!

Menilai dengan deskripsi dan komentar Anda, Anda mungkin akan terbantu dengan deskripsi yang tepat tentang bagaimana pengurangan dapat digunakan untuk membuktikan kelengkapan NP:

Masalahnya adalah NP-complete iff di NP dan NP-hard. Ini berarti bahwa bukti kelengkapan NP memiliki dua bagian: bukti bahwa masalahnya terletak pada NP dan bukti bahwa NP-hard.

Untuk bagian pertama, Anda harus menunjukkan bahwa instance-YES dapat diverifikasi dalam waktu polinomial menggunakan beberapa sertifikat yang sesuai. Atau, Anda dapat menunjukkan masalah dapat diselesaikan dalam waktu polinomial oleh mesin Turing non-deterministik, tetapi ini biasanya tidak dilakukan karena kesalahan mudah dilakukan.

Dalam kasus Anda, ini datang untuk membuktikan bahwa untuk setiap grafik dengan -clique, Anda dapat menemukan beberapa bukti bahwa memang ada klik seperti itu, sehingga, dengan dipersenjatai dengan bukti seperti itu, Anda dapat memeriksa dalam waktu polinomial yang memang ada klik seperti itu.$n/2$

Untuk bagian kedua, Anda harus menunjukkan bahwa masalahnya adalah NP-hard. Ini dalam hampir semua kasus ditunjukkan dengan membuktikan bahwa masalah Anda setidaknya sama sulitnya dengan beberapa masalah NP-keras lainnya. Jika SETENGAH-CLIQUE paling tidak sekeras CLIQUE, itu juga harus NP-keras.

Anda melakukan ini dengan membuktikan pengurangan DARI CLIQUE, TO HALF-CLIQUE. Anda 'mengurangi' masalahnya, membuatnya 'lebih mudah'. Anda mengatakan "Memecahkan CLIQUE itu sulit, tetapi saya telah membuktikan bahwa Anda hanya perlu memecahkan SETENGAH-CLIQUE untuk menyelesaikan CLIQUE". (banyak orang, bahkan para ahli, sesekali mengatakan ini dengan cara yang salah :))

Ada berbagai jenis reduksi: reduksi yang paling umum digunakan adalah reduksi di mana Anda memetakan instance dalam hal ini CLIQUE ke instance HALF-CLIQUE yang ukurannya paling besar secara polinomi lebih besar, dalam waktu polinomial. Ini berarti bahwa jika kita dapat memecahkan SETENGAH-CLIQUE, maka kita juga dapat memecahkan CLIQUE dengan merantai algoritma dan pengurangan.

Dengan kata lain, kita harus menunjukkan bahwa kita dapat menyelesaikan CLIQUE jika kita dapat memecahkan SETENGAH-CLIQUE. Kami melakukan ini dengan menunjukkan bahwa untuk setiap instance untuk CLIQUE, kami dapat mendesain instance HALF-CLIQUE sehingga instance CLIQUE adalah instance 'ya' jika instance HALF-CLIQUE adalah instance 'yes'.

Oleh karena itu buktinya dimulai seperti ini: diberi grafik , saya dapat membuat beberapa grafik sedemikian sehingga berisi -clique iff berisi -clique. Saya akan menyerahkan bagian ini kepada Anda (ini adalah bagian yang membutuhkan kreativitas, bagian tentang masalah spesifik yang dihadapi).$G=(V, E)$$H=(V', E')$$G$$k$$H$$n/2$

Kamu sepertinya sedikit tersesat. Anda ingin menunjukkan bahwa HALF-CLIQUE CLIQUE, yang berarti bahwa Anda mencari algoritma poli-waktu yang menggunakan instance CLIQUE sebagai input dan output instance HALF-CLIQUE dengan properti yang "ya" input petakan menjadi "ya" es dan "tidak" memasukkan peta ke "tidak".$\ge$

$G$$k$$H$$H$$G$$k$

Spoiler di bawah ini berisi petunjuk tentang cara melakukan pengurangan ini:

$H$$G$

Anda dapat mengurangi dari masalah penutup simpul. Jika grafik komplemen dari grafik yang diberikan memiliki simpul penutup kurang dari n / 2 node maka grafik ini akan memiliki klik lebih dari n / 2 node yang akan menjadi setengah klik. Nyatakan bahwa sulit untuk menyelesaikan masalah Cover Vertex begitu juga ini.