This is a follow-up to this question. Even though BPTIME does not have a time hierarchy theorem, the reasons that prevent it from having one are essentially bypassed by PromiseBPTIME. Thus, does PromiseBPTIME have a hierarchy theorem? If so, how does it look like and how to prove it?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Have you tried proving such a theorem? Try to emulate the proof of the time hierarchy theorem. $\endgroup$– Yuval FilmusCommented Dec 3, 2020 at 9:19
Add a comment
|