1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Have you tried proving such a theorem? Try to emulate the proof of the time hierarchy theorem. $\endgroup$ – Yuval Filmus Dec 3 '20 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.