Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with heuristic algorithms:
TR06-131 | 6th October 2006
Konstantin Pervyshev

On Heuristic Time Hierarchies

We study the existence of time hierarchies for heuristic (average-case) algorithms. We prove that a time hierarchy exists for heuristics algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Earlier, Fortnow and Santhanam (FOCS'04) proved the existence of a time hierarchy for ... more >>>

TR14-178 | 5th December 2014
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Heuristic time hierarchies via hierarchies for sampling distributions

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 ... more >>>

ISSN 1433-8092 | Imprint