Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TIME HIERARCHY:
Reports tagged with time hierarchy:
TR05-076 | 2nd July 2005
Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

#### Time hierarchies for cryptographic function inversion with advice

We prove a time hierarchy theorem for inverting functions
computable in polynomial time with one bit of advice.
In particular, we prove that if there is a strongly
one-way function, then for any k and for any polynomial p,
there is a function f computable in linear time
with one ... more >>>

TR05-111 | 3rd October 2005
Dieter van Melkebeek, Konstantin Pervyshev

#### A Generic Time Hierarchy for Semantic Models With One Bit of Advice

We show that for any reasonable semantic model of computation and for
any positive integer $a$ and rationals $1 \leq c < d$, there exists a language
computable in time $n^d$ with $a$ bits of advice but not in time $n^c$
with $a$ bits of advice. A semantic ... more >>>

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

TR08-073 | 4th August 2008
Dmitry Itsykson

#### Structural complexity of AvgBPP

We study class AvgBPP that consists of distributional problems that can be solved in average polynomial time (in terms of Levin's average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for AvgBPP under polynomial-time samplable distributions. Since we use deterministic ... 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