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

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$. This is the {\em unbalanced} analogue ... 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$, and $\NSC$ (the nondeterministic version of SC). ... 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 (sets) ... more >>>