All reports by Author Lane A. Hemaspaandra:

__
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-027
| 20th February 1996
__

Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman#### Computing Solutions Uniquely Collapses the Polynomial Hierarchy

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

Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

Is there an NP function that, when given a satisfiable formula

as input, outputs one satisfying assignment uniquely? That is, can a

nondeterministic function cull just one satisfying assignment from a

possibly exponentially large collection of assignments? We show that if

there is such a nondeterministic function, then the polynomial ...
more >>>