Consequences of UP equals NP

Question

EDIT at 2011/02/08: After some references finding and reading, I decided to separate the original question into two separate ones. Here's the part concerning UP vs NP, for the syntactic and semantic classes part please see Benefits for syntactic and semantic classes.

---

$\mathsf{UP}$ (the unambiguous polynomial time, see wiki and the zoo for references) is defined as languages decided by $\mathsf{NP}$-machines with an additional constrain that

• There is at most one accepting computation path on any input.

The precise relations between $\mathsf{P}$ vs $\mathsf{UP}$ and $\mathsf{UP}$ vs $\mathsf{NP}$ are still open. We know that worst-case one-way functions exist if and only if $\mathsf{P} \neq \mathsf{UP}$, and there are oracles relative to all possibilities of the inclusions $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{NP}$.

I'm interested in why $\mathsf{UP}$ vs $\mathsf{NP}$ is an important question. People tend to believe (at least in literature) that these two classes are different, and my problem is:

If $\mathsf{UP} = \mathsf{NP}$, are there any "bad" consequences happened?

There is a related post on complexity blog in 2003. And if my understanding is correct, the result by Hemaspaandra, Naik, Ogiwara and Selman shows that if

• There is an $\mathsf{NP}$ language $L$ such that for each satisfiable formula $\phi$ there is a unique satisfying assignment $x$ with $(\phi,x)$ in $L$,

then the polynomial hierarchy collapses to the second level. No such implication is known if $\mathsf{UP} = \mathsf{NP}$ holds.

Answer 1

It is known that $\mathsf{UP= NP}$ implies $\mathsf{SpanP = \#P}$ since Kobler, Schoning, and Toran proved that $\mathsf{UP= NP}$ if and only if $\mathsf{SpanP = \#P}$. It is easy to see that $\mathsf {\#P}$ is contained in $\mathsf {SpanP}$.

A function $f : Σ^* →\mathbb N$ is in $\mathsf{SpanP}$ if there is an $\mathsf {NP}$ Turing machine transducer $M$ such that for all $x$, $f(x)$ is the number of distinct outputs of $M$ on input $x$.

J. Kobler, U. Schoning, and J. Toran. On counting and approximation, Acta Informatica, 26:363-379, 1989.