Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALTERNATING TURING MACHINES:
Reports tagged with alternating Turing machines:
TR95-005 | 1st January 1995
Maciej Liskiewicz, Rüdiger Reischuk

#### The Sublogarithmic Alternating Space World

This paper tries to fully characterize the properties and relationships
of space classes defined by Turing machines that use less than
logarithmic space - may they be deterministic,
nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages ... more >>>

TR12-007 | 28th January 2012
Ruiwen Chen, Valentine Kabanets

#### Lower Bounds against Weakly Uniform Circuits

Revisions: 1

A family of Boolean circuits $\{C_n\}_{n\geq 0}$ is called \emph{$\gamma(n)$-weakly uniform} if
there is a polynomial-time algorithm for deciding the direct-connection language of every $C_n$,
given \emph{advice} of size $\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one
to interpolate between complete uniformity (when $\gamma(n)=0$) ... more >>>

ISSN 1433-8092 | Imprint