Pertanyaan ini mungkin tidak bersifat teknis. Sebagai pembicara non-asli dan TA untuk kelas algoritma, saya selalu bertanya-tanya apa arti gadget dalam 'gadget klausa' atau 'gadget variabel'. Kamus mengatakan gadget adalah mesin atau perangkat, tapi saya tidak yakin apa artinya bahasa sehari-hari dalam konteks bukti NP-complete.
cc.complexity-theory
np-hardness
terminology
reductions
Federico Magallanez
sumber
sumber
Jawaban:
"Gadget" adalah perangkat khusus kecil untuk beberapa tugas tertentu. Dalam bukti NP-hardness, ketika melakukan pengurangan dari masalah A ke masalah B, istilah sehari-hari "gadget" mengacu pada contoh kecil (parsial) dari masalah B yang digunakan untuk "mensimulasikan" objek tertentu dalam masalah A. Misalnya, ketika mengurangi 3SAT menjadi 3-COLORING, gadget klausa adalah grafik kecil yang digunakan untuk mewakili klausa dari rumus asli dan gadget variabel adalah grafik kecil yang digunakan untuk mewakili variabel dari rumus asli. Untuk memastikan bahwa pengurangan itu benar, gadget harus berupa grafik yang dapat berwarna 3 dengan cara yang sangat spesifik. Karenanya kami menganggap grafik kecil ini sebagai perangkat yang melakukan tugas khusus.
Dalam banyak kasus, kesulitan utama membuktikan NP-hardness adalah membangun gadget yang sesuai. Terkadang gadget ini rumit dan cukup besar. Proses kreatif pembuatan gadget semacam itu terkadang disebut "gadgeteering."
sumber
Definisi formal Gadget untuk pengurangan optimasi NP muncul di sini:
L. Trevisan, GB Sorkin, M. Sudan, DP Williamson. Gadget, Perkiraan, dan Pemrograman Linear . SIAM J. on Computing, 29 (6): 2074-2097, 2000
sumber