Amihood Amir, Richard Beigel, William Gasarch

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

Till Tantau

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

Elmar Böhler, Christian Glaßer, Daniel Meister

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