We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:

• 1-tt-mitoticity and m-mitoticity differ on NP.
• 1-tt-reducibility and m-reducibility differ on NP.
• There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither T-mitotic nor m-mitotic).
... more >>>

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 propose the e-model for leaf languages which generalizes the known balanced and unbalanced concepts. Inspired by the neutral behavior of rejecting paths of NP machines, we allow transducers to output empty words. The paper explains several advantages of the new model. A central aspect is that it allows us ... 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 >>>