Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Enumerability:
TR00-024 | 16th May 2000
Amihood Amir, Richard Beigel, William Gasarch

Some Connections between Bounded Query Classes and Non-Uniform Complexity

Let A(x) be the characteristic function of A. Consider the function
F_k^A(x_1,...,x_k) = A(x_1)...A(x_k). We show that if F_k^A can be
computed with fewer than k queries to some set X, then A can be
computed by polynomial size circuits. A generalization of this result
has applications to bounded query ... more >>>

TR03-024 | 25th February 2003
Till Tantau

Weak Cardinality Theorems for First-Order Logic

Kummer's cardinality theorem states that a language is recursive
if a Turing machine can exclude for any n words one of the
n + 1 possibilities for the number of words in the language. It
is known that this theorem does not hold for polynomial-time
computations, but there ... more >>>

TR03-069 | 13th August 2003
Elmar Böhler, Christian Glaßer, Daniel Meister

Small Bounded-Error Computations and Completeness

SBP is a probabilistic promise class located
between MA and AM \cap BPPpath. The first
part of the paper studies the question of whether
SBP has many-one complete sets. We relate
this question to the existence of uniform
enumerations. We construct an oracle relative to
which SBP and AM do ... more >>>

ISSN 1433-8092 | Imprint