Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-004 | 17th January 2025 19:35

A note on a hierarchy theorem for promise-BPTIME

RSS-Feed




TR25-004
Authors: Songhua He
Publication: 19th January 2025 19:20
Downloads: 181
Keywords: 


Abstract:

We prove a time hierarchy theorem for the promise-BPTIME. This is considered to be a folklore problem and was thought to follow from the existence of complete problems or through direct diagonalization. We observe that neither argument carries through in some immediate way in the promise version. However, the hierarchy theorem can be proved by the standard delayed diagonalization for the nondeterministic time hierarchy theorem [Coo72, SFM78, Zak83], or, as it was observed by Rahul Santhanam, from the established BPTIME hierarchies with advice [Bar02, FS04, GST11, FST05, Per05, vMP07, San25].



ISSN 1433-8092 | Imprint