Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR96-060 | 19th November 1996
Bernd Borchert, Frank Stephan

Looking for an Analogue of Rice's Theorem in Complexity Theory

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.

more >>>

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

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

TR96-033 | 6th March 1996
Bernd Borchert, Desh Ranjan, Frank Stephan

On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

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.

more >>>

TR96-006 | 24th January 1996
Bernd Borchert, Antoni Lozano

Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept

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

ISSN 1433-8092 | Imprint