Bernd Borchert
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Bernd Borchert has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Frank Stephan
National University of Singapore
2 shared publications - Antoni Lozano
Universitat Politecnica de Catalunya
1 shared publication - Desh Ranjan
Department of Computer Science, New Mexico State University, Las Cruces, NM 88003, USA
1 shared publication - Dietrich Kuske
Institut für Algebra, Technische Universität Dresden, D-01062 Dresden, Germany
1 shared publication - Joerg Rothe
Friedrich-Schiller-Universität Jena
1 shared publication - Lane A. Hemaspaandra
University of Rochester, Rochester, NY, USA
1 shared publication
Latest Publications
- Open Access
Restrictive Acceptance Suffices for Equivalence Problems
One way of suggesting that an NP problem may not be NP-complete is to show that it is in the class UP. We suggest an analogous new approach---weaker in strength of evidence but more broadly applicable---to suggesting that concrete~NP problems are not NP-complete. In particular we introduce the class 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. Since if any NP-complete set is in EP then all NP sets are in EP, it follows---with whatever degree of strength one believes that EP differs from NP---that membership in EP can be viewed as evidence that a problem is not NP-complete. We show that the negation equivalence problem for OBDDs (ordered binary decision diagrams) and the interchange equivalence problem for 2-dags are in EP. We also show that for boolean negation the equivalence problem is in EP^{NP}, thus tightening the existing NP^{NP} upper bound. We show that FewP, bounded ambiguity polynomial time, is contained in EP, a result that is not known to follow from the previous SPP upper bound. For the three problems and classes just mentioned with regard to EP, no proof of membership/containment in UP is known, and for the problem just mentioned with regard to EP^{NP}, no proof of membership in UP^{NP} is known. Thus, EP is indeed a tool that gives evidence against NP-completeness in natural cases where UP cannot currently be applied.
Open AccessRestrictive Acceptance Suffices for Equivalence Problems
One way of suggesting that an NP problem may not be NP-complete is to show that it is in the class UP. We suggest an analogous new approach---weaker in strength of evidence but more broadly applicable---to suggesting that concrete~NP problems are not NP-complete. In particular we introduce the class 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. Since if any NP-complete set is in EP then all NP sets are in EP, it follows---with whatever degree of strength one believes that EP differs from NP---that membership in EP can be viewed as evidence that a problem is not NP-complete. We show that the negation equivalence problem for OBDDs (ordered binary decision diagrams) and the interchange equivalence problem for 2-dags are in EP. We also show that for boolean negation the equivalence problem is in EP^{NP}, thus tightening the existing NP^{NP} upper bound. We show that FewP, bounded ambiguity polynomial time, is contained in EP, a result that is not known to follow from the previous SPP upper bound. For the three problems and classes just mentioned with regard to EP, no proof of membership/containment in UP is known, and for the problem just mentioned with regard to EP^{NP}, no proof of membership in UP^{NP} is known. Thus, EP is indeed a tool that gives evidence against NP-completeness in natural cases where UP cannot currently be applied.
- 1 November 1998
- Published by Springer Nature in Theory of Computing Systems
- Vol. 31 (6) , 679-693
On the Computational Complexity of Some Classical Equivalence Relations on Boolean Functions
- 1 November 1998
- Published by Springer Nature in Theory of Computing Systems
- Vol. 31 (6) , 679-693
On the Computational Complexity of Some Classical Equivalence Relations on Boolean Functions
- 1 January 1998
- Published by Springer Nature
- p. 17-28
On existentially first-order definable languages and their relation to NP
- 1 January 1998
- Published by Springer Nature
- p. 17-28
On existentially first-order definable languages and their relation to NP
- 14 August 1997
- Published by Elsevier in Information Processing Letters
- Vol. 63 (3) , 153-158
A characterization of the leaf language classes
- 14 August 1997
- Published by Elsevier in Information Processing Letters
- Vol. 63 (3) , 153-158
A characterization of the leaf language classes
- 26 August 1996
- Published by Elsevier in Information Processing Letters
- Vol. 59 (4) , 211-215
Succinct circuit representations and leaf language classes are basically the same concept
- 26 August 1996
- Published by Elsevier in Information Processing Letters
- Vol. 59 (4) , 211-215
Succinct circuit representations and leaf language classes are basically the same concept
- 4 September 1995
- Published by Elsevier in Theoretical Computer Science
- Vol. 148 (2) , 207-225
On the acceptance power of regular languages
- 4 September 1995
- Published by Elsevier in Theoretical Computer Science
- Vol. 148 (2) , 207-225
On the acceptance power of regular languages