Hierarchiesatz für NTIME überschneiden coNTIME?

8

Gilt ein Satz in der folgenden Richtung: Wenn g(n) etwas größer als f(n) , dann ist NTIME(g)coNTIME(g)NTIME(f)coNTIME(f) ?

Es ist leicht zu zeigen, dass NPcoNPNEXPcoNEXP . Beweis: Nicht annehmen. Dann

NEXPcoNEXPNPcoNPNPcoNPNEXPcoNEXP,
also NP=coNP und damit (durch Auffüllen) NEXP=coNEXP . Aber dann impliziert unsere Annahme, dass NP=NEXP , was dem Satz der nichtdeterministischen Zeithierarchie widerspricht. QED.

Aber ich sehe nicht einmal, wie man NPcoNP von NSUBEXPcoNSUBEXP , da die Diagonalisierung in dieser Einstellung schwierig erscheint.

William Hoza
quelle
7
Der Schnittpunkt ist eine semantische Klasse, und wir wissen nicht, wie Hierarchiesätze für semantische Klassen bewiesen werden können .
Kaveh

Antworten:

1

(Dies wäre ein Kommentar gewesen, aber er wird nicht richtig gerendert, wenn ich das versuche.)

"Ich sehe nicht einmal, wie man trennt"aus der linearen Exponentenversion von QIP [2] die Linearexponentenversion von coQIP [2].UquasiLIN coUquasiLIN
[][]


quelle