Gilt ein Satz in der folgenden Richtung: Wenn etwas größer als , dann ist ?
Es ist leicht zu zeigen, dass . Beweis: Nicht annehmen. Dann
also und damit (durch Auffüllen) . Aber dann impliziert unsere Annahme, dass , was dem Satz der nichtdeterministischen Zeithierarchie widerspricht. QED.
Aber ich sehe nicht einmal, wie man von , da die Diagonalisierung in dieser Einstellung schwierig erscheint.
cc.complexity-theory
time-complexity
nondeterminism
time-hierarchy
hierarchy-theorems
William Hoza
quelle
quelle
Antworten:
(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].U q uasiLIN ∩coUquasiLIN
[ ]∩[ ]
quelle