This paper is motivated by the open question
whether the union of two disjoint NP-complete sets always is
NP-complete. We discover that such unions retain
much of the complexity of their single components. More precisely,
they are complete with respect to more general reducibilities.

We introduce the polynomial-time tree reducibility
(ptt-reducibility). Our main result states that for
languages $B$ and $C$ it holds that
$B$ ptt-reduces to $C$ if and only if
the unbalanced leaf-language class of $B$ is robustly contained in
the unbalanced leaf-language class of $C$.
... more >>>

Given a fixed computable binary operation f, we study the complexity of the following generation problem: The input consists of strings a1,...,an,b. The question is whether b is in the closure of {a1,...,an} under operation f.

For several subclasses of operations we prove tight upper and lower bounds for the ... more >>>

Motivated by the question of how to define an analog of interactive
proofs in the setting of logarithmic time- and space-bounded
computation, we study complexity classes defined in terms of
operators quantifying over oracles. We obtain new
characterizations of $\NCe$, $\L$, $\NL$, $\NP$, ... more >>>

We define and examine several probabilistic operators ranging over sets
(i.e., operators of type 2), among them the formerly studied
ALMOST-operator. We compare their power and prove that they all coincide
for a wide variety of classes. As a consequence, we characterize the
ALMOST-operator which ranges over infinite objects ... more >>>