Gerd Wechsung

MFCS Conference 2000 Conference Paper

Reducing the Number of Solutions of NP Functions

• Lane A. Hemachandra
• Mitsunori Ogihara
• Gerd Wechsung

Abstract We study whether one can prune solutions from NP functions. Though it is known that, unless surprising complexity class collapses occur, one cannot reduce the number of accepting paths of NP machines [ 17 ], we nonetheless show that it often is possible to reduce the number of solutions of NP functions. For finite cardinality types, we give a sufficient condition for such solution reduction. We also give absolute and conditional necessary conditions for solution reduction, and in particular we show that in many cases solution reduction is impossible unless the polynomial hierarchy collapses.

FOCS Conference 1997 Conference Paper

The Minimization Problem for Boolean Formulas

• Edith Hemaspaandra
• Gerd Wechsung

We investigate the computational complexity of the minimization problem for Boolean formulas. Depending on the definition, these problems are trivially in /spl Sigma//sub 2//sup P/ or II/sub 2//sup P/, and these are the best upper bounds known. The only previously known lower bounds are also trivial, and are coNP lower bounds at best, thus leaving quite a large gap between the upper and lower bounds. In this paper, we prove much better lower bounds: hardness for parallel access to NP for those cases in which coNP was the best previously known lower bound, and coNP-hardness for the case in which no lower bound was previously known.

I&C Journal 1997 Journal Article

Time Bounded Frequency Computations

• Maren Hinrichs
• Gerd Wechsung

(1) We obtain two new results concerning the inclusion problem of polynomial time frequency classes with equal numbers of errors. 1. (m, m+d) P⊉(m+1, m+d+1) Pform<2 d. 2. (m, m+d) P=(m+1, m+d+1) Pform⩾c(d) wherec(d) is large enough. This disproves a conjecture of Kinber. (2) We give a transparent proof of a generalization of Kinber's result that there exist arbitrarily complex problems admitting a polynomial time frequency computation. Several corollaries provide more insight into the structure of the hierarchy of polynomial time frequency classes. (3) The relationships between polynomial time frequency classes and selectivity classes are studied.

MFCS Conference 1992 Conference Paper

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

• Waldemar Preilowski
• Elias Dahlhaus
• Gerd Wechsung

Abstract Let S be a set of n given points in 3-dimensional space. We present parallel algorithms for the construction of the convex hull and for triangulation of S on a CREW-PRAM. For 3-dim. convex hull our algorithm is time-optimal and uses time O(1/ε· log(n)) with O ( n 1+e ) processors. By duality parallel convex hull algorithms induce new ones for Voronoidiagrams in the plane, using the same time and processor bounds. A second parallel algorithm for Voronoi-diagrams presented here uses time O(log(n) 2 ) with O(n) processors. For 3-dim. triangulation of S we give the first parallel algorithm for the generalized problem, using time O ( log(n) 2 ) with O ( n 1+e ) processors. For the tangential-plane problem we give a parallel algorithm, needing time O(log(n)) with O(n) processors.

TCS Journal 1991 Journal Article

Kolmogorov characterizations of complexity classes

• Lane A. Hemachandra
• Gerd Wechsung

This paper completely characterizes the Θ k p levels of the polynomial hierarchy in terms of Kolmogorov complexity. From the characterization, it follows that the Θ k p and Δ k p levels of the polynomial hierarchy are equal if and only if every Δ k p language is accepted by some Δ k p machine whose pronouncements (query answers) are Kolmogorov simple. Analogous results are obtained for the exponential hierarchy.

MFCS Conference 1986 Conference Paper

Nondeterministic Turing Machines with Modified Acceptance

• Thomas Gundermann
• Gerd Wechsung

Abstract The complexity classification of problems defined by restricting NP-complets problems to those instances having unique solutions requires still finer hierarchies within BC(NP) (the Boolean closure of NP) than that introduced in [Wec 85] (see also [WeWa 85], [GuWe 85], [CaHe 85] and [KöSc 85]) which will be called the Hausdorff hierarchy generated by NP. In this paper an extremely fine hierarchy within BC(NP) is proposed. The classes of this hierarchy are characterized by nondeter-ministic polynomial time Turing machines with suitably modified acceptance notions (Section 2). Complete sets for the classes of the hierarchy are presented in Section 5. The hierarchy is studied under relativizations (Sections 3 and 5). Section 4 yields more insight in the structure of the hierarchy.

MFCS Conference 1979 Conference Paper

A Crossing Measure for 2-Tape Turing Machines

• Gerd Wechsung

TCS Journal 1979 Journal Article

A relation between space, return and dual return complexities

• Gerd Wechsung
• Andreas Brandstädt

We introduce the dual return complexity and prove that the return complexity classes and the dual return complexity classes of nondeterministic Turing machines coincide with the tape complexity classes of Turing machines with auxiliary pushdown tape for resource functions ƒ⩾id, id being the identity function.

MFCS Conference 1977 Conference Paper

Complexity Hierarchies of Oracles

• Klaus W. Wagner
• Gerd Wechsung

MFCS Conference 1977 Invited Paper

Properties of Complexity Classes: A Short Survey

• Gerd Wechsung

Abstract This short survey of properties of complexity classes (CC's for short) does not pretend to be complete. We rather confine ourselves to the illustration of important features by typical examples. Simultaneously an attempt is made to find a reasonable systematization of the vast variety of papers contributing to our topic. Among the chosen examples there are four so far unpublished statements (numbered (5), (6), (19) and (35)) about the return complexity [70] and a new measure A for nondeterministic Turing machines (NDTM) which is similar to the return complexity.

MFCS Conference 1975 Conference Paper

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

• Gerd Wechsung

MFCS Conference 1975 Conference Paper

The Axiomatization Problem of a Theory of Linear Languages

• Gerd Wechsung