Persimpangan bahasa dalam NP

8

Bisakah perpotongan dua bahasa dalam NP yang tidak lengkap menjadi NP lengkap?

Bisakah perpotongan dua bahasa dalam coNP yang bukan coNP selesai menjadi coNP lengkap?

Dapatkah perpotongan dua bahasa satu dalam coNP tetapi tidak lengkap dan lainnya dalam NP tetapi tidak lengkap NP menjadi NP lengkap atau coNP lengkap?

complexity-classes np T ....
sumber
Sangat menarik. :)
Michael Wehar
2
Jika P = NP, maka jawabannya adalah TIDAK. Dalam hal ini, satu-satunya bahasa yang tidak lengkap NP (coNP-complete) adalah set kosong dan . Σ∗
Gamow
3
Jika P tidak sama dengan NP, maka oleh ladners, masalah NP intermidiate memang ada ... contoh apa pun yang Anda sarankan tentang yang alami. Satu.
ARi

Jawaban:

19

Hanya komentar yang diperluas untuk lebih menjelaskan komentar ARi (saya sedang menulis sementara saya melihatnya).

Cukuplah menggunakan pendekatan "celah besar" yang serupa dengan yang digunakan dalam teorema Lardner; sebagai contoh:

A1={x∣x∈SAT∧f(|x|) is even}∪{x∣f(|x|) is odd}

A2={x∣x∈SAT∧f(|x|) is odd}∪{x∣f(|x|) is even}

Di mana adalah fungsi yang meningkat cukup lambat dihitung dalam waktu polinomial. Lihat misalnya konstruksinya dalam bukti teorema Ladner di Lampiran A.1 dari Bahasa Seragam yang Keras .f

Dengan konstruksi bukan NPC, tetapi A 1 ∩ A 2 = S A TA1,A2A1∩A2=SAT

Marzio De Biasi
sumber
2
mengapa dan A 2 bukan NPC? A1A2
Mateus de Oliveira Oliveira
@MateusdeOliveiraOliveira: dengan diagonalisasi tertunda bukan NPC ( A 1 adalah masalah intermediate NP buatan); lihat bukti tertaut untuk detailnya. Tentu saja, kita harus mengasumsikan bahwa P ≠ N P ; kasus P = N P telah dikesampingkan oleh Gamow dalam komentar di atas. {x∣x∈SAT∧f(|x|) is even}A1P≠NPP=NP
Marzio De Biasi
Tidak bisakah hanya tentang fungsi polytime?
ARi
@ ARi: tidak, itu harus cukup lambat untuk membuat celah besar untuk mencegah kelengkapan NP (untuk memungkinkan diagonalisasi tertunda). Saya akan mencoba menulis bukti formal di hari-hari berikutnya.
Marzio De Biasi
f