Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR05-035 | 24th March 2005
Christian Glaßer, Stephen Travers, Klaus W. Wagner

A Reducibility that Corresponds to Unbalanced Leaf-Language Classes

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

TR04-037 | 14th April 2004
Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner

Generation Problems

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

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

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

TR96-035 | 27th March 1996
Ronald V. Book, Heribert Vollmer, Klaus W. Wagner

Probabilistic Type-2 Operators and ``Almost''-Classes

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

ISSN 1433-8092 | Imprint