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$ Have you tried proving such a theorem? Try to emulate the proof of the time hierarchy theorem. $\endgroup$ Dec 3, 2020 at 9:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.