Masalah keputusan NP apa yang tidak dapat direduksi sendiri?

8

Jadi kami baru belajar tentang reducibilitas diri di kelas. Profesor saya dan buku teks kami tidak akan berkomitmen untuk mengatakan bahwa semua masalah dalam NP dapat direduksi sendiri, tetapi sepertinya tidak ada contoh masalah yang tidak. Saya bertanya-tanya apakah ada contoh, atau hanya situasi di mana Anda tidak dapat membuktikan negatif dengan mudah. Wikipedia hanya mengatakanIt is conjectured that the integer factorization problem is not self-reducible.

Googling menemukan satu hasil , yang tampaknya menyatakan bahwa pewarnaan planar grafik 4 tidak dapat direduksi sendiri karena pewarnaan LF-k untuk grafik planar berkurang menjadi pengurangan itu, tetapi saya tidak bisa mengikuti buktinya sekarang.

Apakah ini contoh aktual dari penolakan kemampuan reduksi diri, dan adakah yang lain?

complexity-theory reductions decision-problem np Adam Martin
sumber
@ DW Tidak, hanya reduksi diri. Baca koran.
Yuval Filmus

Jawaban:

3

Makalah ini memang menunjukkan bahwa planar graph empat pewarnaan tidak dapat direduksi sendiri dalam arti Schnorr. Ada beberapa indera lain, di mana beberapa di antaranya setiap masalah dalam P dapat direduksi sendiri. Lihat makalah tindak lanjut dari Große, Rothe dan Wechsung . Saya tidak mengetahui adanya hasil lain dari jenis ini. Membahas semua makalah yang mengutip makalah yang Anda sebutkan (ini dapat dilakukan dengan menggunakan Google Cendekia, misalnya), tidak ada yang memberikan masalah seperti itu.

Yuval Filmus
sumber
Terima kasih! Pertanyaan singkat, apakah pemahaman saya tentang bagian utama dari bukti mereka benar, atau apakah saya tidak mengikutinya dengan benar? Kami belum melakukan banyak hal dengan definisi bahasa formal yang sebenarnya, kami sudah sedikit lebih abstrak sehingga sulit untuk merasa percaya diri dalam tingkat detail ini. (Juga hanya akan menunggu sedikit untuk menerima jawaban karena saya memiliki pengetahuan materi pelajaran minimal dan ingin menunggu untuk melihat apakah orang lain berpadu.)
Adam Martin
Jika masalah dapat direduksi sendiri dalam arti Schnorr dan versi keputusan dapat diselesaikan dalam waktu polinomial, maka Anda dapat menemukan solusi leksikografis pertama dalam waktu polinomial. Ini bertumpu pada definisi khusus Schnorr. Dalam hal ini versi keputusan sangat mudah (jawabannya selalu YA) sedangkan versi lex-first adalah NP-hard, sehingga masalahnya tidak dapat direduksi sendiri kecuali P = NP.
Yuval Filmus
Terima kasih! Saya merasa seperti satu-satunya penghalang yang masih saya miliki adalah indera berbeda dari reducibilitas diri. Haruskah saya mengajukan pertanyaan lain, atau itu perbedaan kecil yang bisa saya tanyakan di sini / edit yang asli? Kami belajar secara luas bahwa suatu masalah dapat direduksi sendiri jika diberi solusi keberadaan polytime, Anda dapat membuat solusi pencarian polytime. Apakah ada perbedaan teknis di sini bahwa hasil ini bergantung pada?
Adam Martin
1
Lihatlah kertas kerja Große et al., Yang membahas hal ini.
Yuval Filmus