Lakukan banyak-satu reduksi dan reduksi Turing menentukan NPC kelas yang sama

11

Saya ingin tahu apakah kelas NPC didefinisikan oleh banyak-satu pengurangan dan pengurangan Turing adalah sama.

Sunting: Pertanyaan lain, apakah pengurangan Turing hanya menciutkan kelas C dan co-C untuk beberapa C atau apakah ada kelas seperti ada masalah tidak dalam C ∪ c o - C di bawah pengurangan Karp dan yang ada di C di bawah pengurangan Turing ?CC∪co−CC

cc.complexity-theory np-hardness reductions Ludovic Patey
sumber
4
Sudahkah Anda membaca en.wikipedia.org/wiki/… ?
Jukka Suomela
Terima kasih atas tautan Anda. Itu menjawab bagian pertama dari pertanyaan saya, tetapi tidak menjawab apakah ada masalah yang muncul dalam co-C di bawah banyak-satu pengurangan dan di C di bawah pengurangan Turing, untuk C.
Ludovic Patey
1
Maaf, ini mungkin tampak pertanyaan mendasar atau mungkin saya tidak berpikir jernih pada jam selarut ini tetapi saya kehilangan sesuatu di artikel wiki. Artikel itu mengatakan bahwa di bawah pengurangan Cook, NP-complete sama dengan co-NP-complete, tapi saya tidak melihatnya. NP-hard sama dengan pengurangan co-NP-hard wrt Cook, tetapi NP-complete berarti keduanya NP-hard DAN NP , dan saya tidak melihat mengapa (misalnya) TAUT akan menggunakan NP? Yaitu TAUT adalah co-NP-hard di bawah pengurangan Cook tapi itu tidak cukup untuk menjadi NP-complete.
Kaveh
@ Monoid, Anda harus menulis ulang pertanyaan Anda untuk mencerminkan klarifikasi ini. Karena itu, pertanyaannya ambigu
Suresh Venkat
duplikat yang mungkin dari Banyak-satu pengurangan vs pengurangan Turing untuk mendefinisikan NPC
Suresh Venkat

Jawaban:

7

Lihatlah pertanyaan ini dan terutama jawaban ini oleh Aaron Sterling. Singkatnya: "mereka diduga sebagai gagasan yang berbeda."

Matthias
sumber
Saya tahu bahwa jika NP! = Co-NP, mereka adalah gagasan yang berbeda karena pengurangan Turing meruntuhkan mereka, tetapi dapatkah ada perbedaan yang tidak akan runtuh, misalnya masalah dalam NPI di bawah banyak-satu pengurangan dan di NPC di bawah pengurangan Turing ?
Ludovic Patey
@ Monoïd: NP ≠ coNP tidak menyiratkan (setidaknya dengan cara yang jelas) bahwa dua pengertian pengurangan berbeda. Saya khawatir Anda membingungkan NP kelas (yang didefinisikan secara independen dari pilihan gagasan reduksi) dengan kelas masalah keputusan yang direduksi menjadi NP (yang tergantung pada pilihan gagasan reduksi).
Tsuyoshi Ito
Ups, komentar saya sebelumnya salah. Jika NP ≠ coNP, dua pengertian reduksi jelas berbeda (SAT tanpa syarat Turing dapat direduksi menjadi UNSAT, tetapi SAT banyak yang dapat direduksi menjadi UNSAT jika dan hanya jika NP = coNP).
Tsuyoshi Ito
10

The "Boolean Hierarchy" BP adalah hirarki seluruh kombinasi dari masalah NP bawah pengurangan Karp yang semuanya di P ^ NP.

Noam
sumber
9

Sejauh yang saya tahu, pertanyaan ini benar-benar terdiri dari dua pertanyaan berbeda, yang pertama muncul di judul dan yang kedua diberikan setelah diedit.

(1) Apakah banyak-satu reduksi dan reduksi Turing mendefinisikan set yang sama dari masalah NP-complete (yaitu masalah yang keduanya dalam NP dan yang SAT dapat dikurangi menjadi)? Apakah NPC di bawah pengurangan Turing sama dengan NPC di bawah banyak-satu pengurangan masih merupakan masalah terbuka tujuh tahun yang lalu, dan saya tidak percaya itu telah ditutup sejak itu. Lihat survei ini dari ACM SIGACT News Juni 2003 untuk perinciannya.

(2) Apa kelas masalah yang memiliki pengurangan Turing untuk, dan sebaliknya? Ini adalah kelas masalah NP-hard (dalam pengurangan Turing) yang ada di P NP . Untuk informasi lebih lanjut tentang ini, lihat jawaban Noam.

Peter Shor
sumber
tautan tidak berfungsi.
T ....
8

Ini tidak menjawab pertanyaan Anda, tetapi orang dapat mengajukan pertanyaan yang sama untuk pengurangan yang lebih lemah. Misalnya, apakah rangkaian masalah NP-lengkap berubah jika kami hanya mengizinkan pengurangan ruang log, atau hanya pengurangan AC 0 , atau bahkan pengurangan NC 0 . Fakta yang mengejutkan adalah bahwa semua masalah NP-complete diketahui selesai bahkan dengan pengurangan NC 0 .

Referensi: Agrawal, M., Allender, E., dan Rudich, S. 1997 Pengurangan dalam Kompleksitas Sirkuit: sebuah Teorema Isomorfisme dan Teorema Gap.

Robin Kothari
sumber
Apakah pertanyaan tentang pengurangan yang lebih lemah ini masih terbuka? Jika saya memiliki masalah yang NP lengkap di bawah pengurangan P / poly atau BPP, tetapi tampaknya tidak di bawah pengurangan P tanpa mengasumsikan asumsi teoritis nomor yang tidak terbukti, apakah ada baiknya membuat catatan?
Peter Shor
@ Peter: Dalam makalah yang saya kutip, dibiarkan terbuka jika ada masalah yang lengkap NP di bawah pengurangan waktu polinomial yang tidak lengkap NP di bawah pengurangan AC ^ 0. Pertanyaan ini telah dijawab dengan Mengurangi kerumitan pengurangan . Mereka menunjukkan masalah yang NP-lengkap dengan pengurangan ACC tetapi bukan pengurangan AC ^ 0. Tidak satu pun dari makalah ini yang mengomentari masalah yang NP-lengkap di bawah pengurangan yang lebih kuat dari waktu polinomial, dan bagaimana hal itu berkaitan dengan kemungkinan NP-lengkap di bawah pengurangan polytime.
Robin Kothari
1

Makalah ini mengklaim menunjukkan bahwa adanya masalah TF N EEXP yang
[cukup sulit untuk diselesaikan dengan nol kesalahan dalam kasus terburuk] menyiratkan adanya
"bahasa lengkap Turing untuk NP yang bukan tabel kebenaran lengkap untuk NP. "

Di sisi lain, saya belum mencoba membaca salah satu bukti yang mereka klaim untuk hasil itu,
tetapi Proposisi 2 dan / atau buktinya menunjukkan kesalahpahaman definisi ZPP :
Sepertinya mereka benar-benar membutuhkan " FP dapat menyelesaikan semua F ZPP ", bukan hanya" ZPP = P ".


sumber