Banyak-satu pengurangan vs pengurangan Turing untuk mendefinisikan NPC

Mengapa kebanyakan orang lebih suka menggunakan banyak-satu reduksi untuk mendefinisikan kelengkapan NP daripada, misalnya, pengurangan Turing?

Dua alasan:

(1) hanya masalah minimal: menjadi NPC di bawah banyak pengurangan adalah pernyataan resmi yang lebih kuat dan jika Anda mendapatkan pernyataan yang lebih kuat (seperti yang dilakukan Karp dan karena Anda hampir selalu melakukannya) maka mengapa tidak mengatakannya?

(2) Berbicara tentang banyak-satu pengurangan menimbulkan hierarki yang lebih kaya, lebih rumit. Misalnya perbedaan NP vs ko-NP menghilang di bawah pengurangan Turing.

Ini mirip dengan semangat mengapa sering kali seseorang menggunakan Logspace-reduksi daripada yang polytime.

Saya tidak tahu apakah ada preferensi, tetapi dugaan itu berbeda pendapat. Artinya, reduksibilitas Turing diperkirakan sebagai gagasan yang lebih kuat. (Ada ada A dan B sehingga A adalah T-direduksi ke B, tetapi tidak mo direduksi menjadi B.) Satu kertas yang dibahas ini adalah satu ini oleh Lutz dan Mayordomo. Mereka mengusulkan penguatan pernyataan P! = NP; kira-kira, NP itu termasuk jumlah EXPTIME yang tidak dapat diabaikan. Asumsi ini memungkinkan mereka untuk menunjukkan bahwa dua konsep reducibilitas berbeda.

Saya pikir alasan orang lebih suka (untuk memulai dengan) banyak-satu pengurangan adalah pedagogis - banyak-pengurangan dari A ke B sebenarnya adalah fungsi pada string, sedangkan pengurangan Turing membutuhkan pengenalan oracle.

Perhatikan bahwa pengurangan Cook (polinomial-time Turing) dan pengurangan Karp-Levin (polynomial-time many-one) diketahui berbeda pada E tanpa syarat, oleh Ko dan Moore, dan secara terpisah oleh Watanabe (sebagaimana dirujuk dalam makalah Lutz dan Mayordomo) dalam tanggapan Aaron Sterling).

Pengurangan Turing lebih kuat daripada pengurangan pemetaan banyak orang dalam hal ini: Pengurangan Turing memungkinkan Anda memetakan bahasa ke pelengkapnya. Sebagai hasilnya ia dapat mengaburkan perbedaan antara (misalnya) NP dan coNP. Dalam makalah asli Cook, dia tidak melihat perbedaan ini (iirc Cook sebenarnya menggunakan formula DNF dan bukan CNF), tetapi mungkin menjadi sangat cepat bahwa ini adalah pemisahan yang penting, dan banyak sekali pengurangan yang membuatnya lebih mudah untuk berurusan dengan ini .

untuk melompat sedikit dari sudut / jawaban lain di sini oleh AS, ini adalah pertanyaan terbuka (juga di sini ) di perbatasan TCS apakah pengurangan Cook ("Turing") berbeda dari pengurangan Karp-Levin ("many-one"), mungkin setara dengan (utama? kunci?) pertanyaan terbuka pemisahan kelas kompleksitas. di sini adalah hasil baru di sepanjang garis ini

Memisahkan Kelengkapan Masak dari Kelengkapan Karp-Levin di bawah Hipotesis Kekerasan Terburuk / Debasis Mandal, A. Pavan, Rajeswari Venugopalan (ECCC TR14-126)

Kami menunjukkan bahwa ada bahasa yang Turing lengkap untuk NP tetapi tidak banyak yang lengkap untuk NP, di bawah hipotesis kekerasan kasus terburuk .

$\Sigma_1$$Q$

Dalam teori kompleksitas, ada juga gagasan tentang "hierarki polinomial", meskipun tidak seperti hierarki aritmetika, ia hanya dikira ada. Ini mengarah ke klasifikasi yang lebih halus daripada "Apakah masalah ini sulit dipecahkan seperti NP?"

Umumnya, pengurangan Many-one (Karp) lebih mudah untuk dirancang karena merupakan bentuk pengurangan terbatas yang membuat satu panggilan dan tugas utama melibatkan mengubah input menjadi pengkodean yang berbeda. Reduksi Turing mungkin melibatkan logika kompleks. Keberadaan set yang lengkap untuk NP di bawah pengurangan Turing tetapi tidak di bawah banyak-pengurangan menunjukkan bahwa P! = NP.

Misalnya, Ketidakpuasan lengkap untuk NP dalam pengurangan Cook tetapi tidak diketahui lengkap untuk NP dalam pengurangan Karp. Jadi, jika Anda membuktikan bahwa tidak ada pengurangan Karp dari SAT ke UNSAT (setara dari UNSAT ke SAT) maka Anda akan membuktikan bahwa NP! = CoNP dan karenanya P! = NP.