All reports by Author Klaus W. Wagner:

__
TR06-069
| 11th May 2006
__

Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner#### The Complexity of Unions of Disjoint Sets

__
TR05-035
| 24th March 2005
__

Christian Glaßer, Stephen Travers, Klaus W. Wagner#### A Reducibility that Corresponds to Unbalanced Leaf-Language Classes

__
TR04-037
| 14th April 2004
__

Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner#### Generation Problems

__
TR98-057
| 10th September 1998
__

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner#### Characterizing Small Depth and Small Space Classes by Operators of Higher Types

__
TR96-035
| 27th March 1996
__

Ronald V. Book, Heribert Vollmer, Klaus W. Wagner#### Probabilistic Type-2 Operators and ``Almost''-Classes

Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner

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.

Christian Glaßer, Stephen Travers, Klaus W. Wagner

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

Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner

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

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

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

Ronald V. Book, Heribert Vollmer, Klaus W. Wagner

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