Sebuah oracle untuk memisahkan NP dari coNP

12

Bagaimana membuktikan bahwa ? Saya hanya mencari oracle TM M dan bahasa rekursif L ( M ) = L yang ini berlaku.NPAcoNPAML(M)=L

Aku tahu buktinya mana Anda menunjukkan bahwa ada sebuah ramalan sehingga P AN P A dan oracle A sehingga P A = N P A . Saya punya petunjuk bahwa saya harus menemukan oracle A dengan memperluas bukti P AN P A tetapi di mana pun saya mencari dan membaca, itu "jelas" atau "langsung" di mana-mana, tetapi saya tidak melihat bagaimana membuktikannya sama sekali .APANPAAPA=NPAAPANPA

stewenson
sumber
6
Tidak jelas apakah Anda telah mengikuti petunjuknya. Saya terkejut mendengar bahwa jelas, tetapi Anda dapat menemukan buktinya dalam (misalnya) Kompleksitas Komputasi: Pendekatan Modern oleh Arora dan Barak. PANPA

Jawaban:

9

coNP

Saya akan menjelaskan modifikasi yang diperlukan di bawah ini, tetapi pertama-tama mari kita lihat sekilas bukti aslinya.

A=nAniiPMi{xyA |x|=|y|}NPA

MiA0mmMimMimMiAmMiA

MicoNPPMiALAMiAMincoNPmA

ADSpace(nω(1))

Kaveh
sumber
3

PA=NPAPBNPBAB

Vincent Russo
sumber