Gerd Wechsung

J. Graph Theory, 2018

2006

On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2006

2003

Relativizing Function Classes.

[BibT_eX]

[DOI]

Christian Glaßer

J. Univers. Comput. Sci., 2003

2002

The Minimization Problem for Boolean Formulas.

[BibT_eX]

[DOI]

Edith Hemaspaandra

SIAM J. Comput., 2002

Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2002

Reducing the Number of Solutions of NP Functions.

[BibT_eX]

[DOI]

Mitsunori Ogihara

J. Comput. Syst. Sci., 2002

2001

A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs

[BibT_eX]

[DOI]

CoRR, 2001

Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Computer Science, 7th Italian Conference, 2001

1999

Robust Reductions.

[BibT_eX]

[DOI]

Jin-yi Cai

Theory Comput. Syst., 1999

Self-Specifying Machines.

[BibT_eX]

[DOI]

Harald Hempel

Int. J. Found. Comput. Sci., 1999

1998

Query Order.

[BibT_eX]

[DOI]

Harald Hempel

SIAM J. Comput., 1998

Embedding ladders and caterpillars into the hypercube.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1998

1997

Time Bounded Frequency Computations.

[BibT_eX]

[DOI]

Maren Hinrichs

Inf. Comput., 1997

The Operators min and max on the Polynomial Hierarchy

[BibT_eX]

[DOI]

Harald Hempel

Electron. Colloquium Comput. Complex., 1997

Easy Sets and Hard Certificate Schemes.

[BibT_eX]

[DOI]

Acta Informatica, 1997

On Sets with Easy Certificates and the Existence of One-Way Permutations.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, Third Italian Conference, 1997

1992

New Parallel Algorithms for Convex Hull and Triangulation in 3-Dimensional Space.

[BibT_eX]

[DOI]

Waldemar Preilowski

Elias Dahlhaus

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

1991

Kolmogorov Characterizations of Complexity Classes.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

Probabilistic Polynomial Time is Closed under Parity Reductions.

[BibT_eX]

[DOI]

Richard Beigel

Inf. Process. Lett., 1991

1990

A Survey on Counting Classes.

[BibT_eX]

[DOI]

Thomas Gundermann

Nasser Ali Nasser

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

The Boolean Hierarchy II: Applications.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

Using Randomness to Characterize the Complexity of Computation.

[BibT_eX]

Proceedings of the Information Processing 89, Proceedings of the IFIP 11th World Computer Congress, San Francisco, USA, August 28, 1989

On the Power of Probabilistic Polynomial Time: P<sup>NP[log]</sup> subseteq PP.

[BibT_eX]

[DOI]

Richard Beigel

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

The Boolean Hierarchy I: Structural Properties.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

1986

Nondeterministic Turing Machines with Modified Acceptance.

[BibT_eX]

[DOI]

Thomas Gundermann

Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

1985

On Sparse Complete Sets.

[BibT_eX]

[DOI]

Math. Log. Q., 1985

On the Boolean closure of NP.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 1985

1980

A Note on the Return Complexity.

[BibT_eX]

J. Inf. Process. Cybern., 1980

1979

A Relation Between Space, Return and Dual Return Complexities.

[BibT_eX]

[DOI]

Andreas Brandstädt

Theor. Comput. Sci., 1979

A Crossing Measure for 2-Tape Turing Machines.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1979, 1979

The oscillation complexity and a hierarchy of context-free languages.

[BibT_eX]

Proceedings of the Fundamentals of Computation Theory, 1979

1977

Properties of Complexity Classes: A Short Survey.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1977, 1977

Complexity Hierarchies of Oracles.

[BibT_eX]

[DOI]

Klaus W. Wagner

Proceedings of the Mathematical Foundations of Computer Science 1977, 1977

A Nonlinear Lower Bound for the Formula Complexity of Certain Boolean Functions.

[BibT_eX]

Proceedings of the Information Processing, 1977

1976

Kompliziertheitstheoretische Charakterisierung der kontextfreien und linearen Sprachen.

[BibT_eX]

J. Inf. Process. Cybern., 1976

1975

Minimale und optimale Blumsche Maße.

[BibT_eX]

J. Inf. Process. Cybern., 1975

Eine algebraische Charakterisierung der linearen Sprachen.

[BibT_eX]

J. Inf. Process. Cybern., 1975

Characterization of Some Classes of Context-Free Languages in Terms of Complexity Classes.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1975, 1975

1974

The Axiomatization Problem of a Theory of Linear Languages.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science, 1974

1973

Funktionen, die von pushdown-Automaten berechnet werden.

[BibT_eX]

[DOI]

Acta Cybern., 1973

Eine verbandstheoretische Klassifikation der längentreuen Wortfunktionen.

[BibT_eX]

[DOI]

Acta Cybern., 1973

Quasisequentielle Funktionen.

[BibT_eX]

[DOI]

Acta Cybern., 1973

1972

Die Gruppe der eineindeutigen längentreuen sequentiellen Funktionen.

[BibT_eX]