19
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (1) It is easy to see (almost by definition) that UP and BPP have complete problems if “problems” can refer to promise problems. They are not known to have complete languages. (2) I do not know the precise definition of syntactic classes. Is PH syntactic? It does not have a complete problem (even with promise) unless the polynomial hierarchy collapses. (3) I do not know your usage of the notation “PromiseUP.” If NP means the class of languages recognized by an NP machine and PromiseUP means the class of promise problems recognized by a UP machine, then clearly they cannot be equal. $\endgroup$ – Tsuyoshi Ito Dec 20 '10 at 12:17
  • $\begingroup$ @Tsuyoshi: Thank you for the questions. (1) By problems I do mean languages, it's my fault that I do not write this clearly. (2) We define syntactic classes as having leaf language characterizations on poly-time machines. PH is special, since no poly-time leaf language characterization is known, where natural complete languages are guaranteed; but PH do have a logspace leaf language characterization. (more) $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 20 '10 at 12:50
  • $\begingroup$ (cont.) (3) Maybe the use of PromiseUP is not correct. Here by PromiseUP I mean a class of languages, such that for yes instances the machine has a unique accepting path, and for no instances the machine have zero or at least two accepting paths. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 20 '10 at 12:51
  • $\begingroup$ Thanks for the reply. As for (3), from a cursory look at the paper by Hemaspaandra, Naik, Ogihara and Selman, I cannot find a way to state the result in terms of decision problems. BTW, the link to the paper is broken. Here is a link to the journal version. $\endgroup$ – Tsuyoshi Ito Dec 20 '10 at 12:59
  • 2
    $\begingroup$ Just to make sure, PromiseUP is completely different from what you described. As I wrote, PromiseUP is the promise-problem version of UP; that is, it is the class of promise problems having a nondeterministic polynomial-time Turing machine M such that for yes-instances M has exactly one accepting path and for no-instances M does not have accepting paths. Although I believe that PromiseUP is the traditional name for this class, some people (including me) write this class simply as UP. $\endgroup$ – Tsuyoshi Ito Dec 20 '10 at 14:16
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.