Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with time hierarchies:
TR00-075 | 7th September 2000
Andreas Klein, Martin Kutrib

Deterministic Turing Machines in the Range between Real-Time and Linear-Time

Deterministic k-tape and multitape Turing machines with one-way,
two-way and without a separated input tape are considered. We
investigate the classes of languages acceptable by such devices with
time bounds of the form n+r(n) where r in o(n) is a sublinear
function. It is shown that there ... more >>>

TR04-093 | 9th November 2004
Oded Goldreich, Madhu Sudan, Luca Trevisan

From logarithmic advice to single-bit advice

Building on Barak's work (Random'02),
Fortnow and Santhanam (FOCS'04) proved a time hierarchy
for probabilistic machines with one bit of advice.
Their argument is based on an implicit translation technique,
which allow to translate separation results for short (say logarithmic)
advice (as shown by Barak) into separations for ... more >>>

TR05-054 | 19th May 2005
Konstantin Pervyshev

Time Hierarchies for Computations with a Bit of Advice

A polynomial time hierarchy for ZPTime with one bit of advice is proved. That is for any constants a and b such that 1 < a < b, ZPTime[n^a]/1 \subsetneq ZPTime[n^b]/1.

The technique introduced in this paper is very general and gives the same hierarchy for NTime \cap coNTime, UTime, ... more >>>

TR07-004 | 12th January 2007
Lance Fortnow, Rahul Santhanam

Time Hierarchies: A Survey

We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes.

more >>>

ISSN 1433-8092 | Imprint