All reports by Author Bernd Borchert:

__
TR97-013
| 13th February 1997
__

Bernd Borchert, Dietrich Kuske, Frank Stephan#### On Existentially First-Order Definable Languages and their Relation to NP

__
TR96-060
| 19th November 1996
__

Bernd Borchert, Frank Stephan#### Looking for an Analogue of Rice's Theorem in Complexity Theory

__
TR96-045
| 28th August 1996
__

Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe#### Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems

Comments: 2

__
TR96-033
| 6th March 1996
__

Bernd Borchert, Desh Ranjan, Frank Stephan#### On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

__
TR96-006
| 24th January 1996
__

Bernd Borchert, Antoni Lozano#### Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept

Bernd Borchert, Dietrich Kuske, Frank Stephan

Pin & Weil [PW95] characterized the automata of existentially

first-order definable languages. We will use this result for the following

characterization of the complexity class NP. Assume that the

Polynomial-Time Hierarchy does not collapse. Then a regular language

L characterizes NP as an unbalanced polynomial-time leaf language

if and ...
more >>>

Bernd Borchert, Frank Stephan

Rice's Theorem says that every nontrivial semantic property

of programs is undecidable. It this spirit we show the following:

Every nontrivial absolute (gap, relative) counting property of circuits

is UP-hard with respect to polynomial-time Turing reductions.

Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe

We study EP, the subclass of NP consisting of those

languages accepted by NP machines that when they accept always have a

number of accepting paths that is a power of two. We show that the

negation equivalence problem for OBDDs (ordered binary decision

diagrams) ...
more >>>

Bernd Borchert, Desh Ranjan, Frank Stephan

The paper analyzes in terms of polynomial time many-one reductions

the computational complexity of several natural equivalence

relations on Boolean functions which derive from replacing

variables by expressions. Most of these computational problems

turn out to be between co-NP and Sigma^p_2.

Bernd Borchert, Antoni Lozano

This note connects two topics of Complexity Theory: The

topic of succinct circuit representations initiated by

Galperin and Wigderson and the topic of leaf languages

initiated by Bovet, Crescenzi, and Silvestri. It will be

shown for any language that its succinct version is

more >>>