Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-178 | 5th December 2014 12:08

Heuristic time hierarchies via hierarchies for sampling distributions

RSS-Feed




TR14-178
Authors: Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Publication: 16th December 2014 20:33
Downloads: 2035
Keywords: 


Abstract:

We give a new simple proof of the time hierarchy theorem for heuristic BPP originally proved by Fortnow and Santhanam [FS04] and then simplified and improved by Pervyshev [P07]. In the proof we use a hierarchy theorem for sampling distributions recently proved by Watson [W13]. As a byproduct we get that P is not included in BPTime[$n^k$] if one way functions exist. As far as we know this statement was not known before.
We also show that our technique may be extended for time hierarchies in some other heuristic classes.



ISSN 1433-8092 | Imprint