Teorema hierarki untuk NTIME berpotongan dengan coNTIME?

8

Apakah teorema di sepanjang baris berikut ini berlaku: Jika g(n) sedikit lebih besar dari f(n) , maka NTIME(g)coNTIME(g)NTIME(f)coNTIME(f) ?

Sangat mudah untuk menunjukkan bahwa NPcoNPNEXPcoNEXP , setidaknya. Bukti: Asumsikan tidak. Kemudian

NEXPcoNEXPNPcoNPNPcoNPNEXPcoNEXP,
jadi NP=coNP , dan karenanya (dengan melapisi) NEXP=coNEXP . Tetapi kemudian asumsi kami menyiratkan bahwa NP=NEXP , bertentangan dengan teorema hierarki waktu nondeterministik. QED.

Tetapi saya bahkan tidak melihat cara memisahkan NPcoNP dari NSUBEXPcoNSUBEXP , karena diagonalisasi tampaknya sulit dalam pengaturan ini.

William Hoza
sumber
7
Persimpangan adalah kelas semantik, dan kami tidak tahu bagaimana membuktikan teorema hierarki untuk kelas semantik .
Kaveh

Jawaban:

1

(Ini sudah menjadi komentar, tetapi tidak diterjemahkan dengan benar ketika saya mencobanya.)

"Aku bahkan tidak melihat cara memisahkan"dari yang linear-eksponen versi QIP [2] versi linear-eksponen dari coQIP [2].UquasiLIN coUquasiLIN
[][]


sumber