<p>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}$.</p>

<p>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$.</p>

<p>J. Kobler, U. Schoning, and J. Toran. <a href="http://link.springer.com/article/10.1007/BF00276023" rel="nofollow">On counting and approximation</a>, Acta Informatica,
26:363-379, 1989.</p>

CC BY-SA 3.0
2014-01-19T02:18:47.947Z
This answer (http://cstheory.stackexchange.com/a/20645/495) also works here since if $UP = NP$ then the disjoint $NP$-pairs conjecture is false.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-19T00:38:47.120Z
2014-01-20T10:26:00.143Z
2014-01-20T10:26:00.143Z
Mohammad Al-Turkistany
<p>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 <a href="https://cstheory.stackexchange.com/q/4792/1800">Benefits for syntactic and semantic classes</a>.</p>

<hr>

<p>$\mathsf{UP}$ (the unambiguous polynomial time, see <a href="http://en.wikipedia.org/wiki/UP_(complexity)" rel="nofollow noreferrer">wiki</a> and <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:U#up" rel="nofollow noreferrer">the zoo</a> for references) is defined as languages decided by $\mathsf{NP}$-machines with an additional constrain that</p>

<ul>
<li>There is at most one accepting computation path on any input.</li>
</ul>

<p>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}$.</p>

<p>I'm interested in why $\mathsf{UP}$ vs $\mathsf{NP}$ is an important question. People tend to believe (at least <a href="http://ccc.cs.uni-duesseldorf.de/~rothe/PDF/26197.pdf" rel="nofollow noreferrer">in</a> <a href="http://www.cs.rochester.edu/~lane/=companion/isolation.pdf" rel="nofollow noreferrer">literature</a>) that these two classes are different, and my problem is:</p>

<blockquote>
  <p>If $\mathsf{UP} = \mathsf{NP}$, are there any "bad" consequences happened?</p>
</blockquote>

<p>There is a related post on <a href="http://blog.computationalcomplexity.org/2003/12/does-npup.html" rel="nofollow noreferrer">complexity blog</a> in 2003. And if my understanding is correct, <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.8999&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">the result</a> by Hemaspaandra, Naik, Ogiwara and Selman shows that if </p>

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

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

CC BY-SA 2.5
2010-12-20T12:17:27.310Z
(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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-20T12:50:15.537Z
@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](http://cstheory.stackexchange.com/q/761/1800) 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)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-20T12:51:26.720Z
(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.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-20T12:59:38.583Z
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](http://dx.doi.org/10.1137/S0097539794268315).
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-20T13:31:59.103Z
@Tsuyoshi: Is the following reasoning correct: If **NP** = **PromiseUP**, then all problems in **NP** reduce to USAT, which is the problem containing all formulas with a unique assignment. Then, given a formula as input, we can output a unique satisfying assignment in **NP** by guessing, which satisfies the requirement of the paper [HNOS96].
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-20T13:55:49.417Z
First, the “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” is called US.  See [my answer to another question](http://cstheory.stackexchange.com/questions/1639/verifying-unique-solutions-of-sat/1641#1641).  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-20T14:04:57.290Z
(cont’d)  Second, I cannot see how the condition NP=US implies Hypothesis 1.1 in [HNOS96].  What I cannot understand is that your function (required for Hypothesis 1.1) seems to be changing the formula, but it is not allowed.  But I must be missing something simple because the introduction of [HNOS96] states that NP=coNP “clearly” implies Hypothesis 1.1 and I cannot see the reason for this either.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-20T14:16:43.633Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-20T14:26:21.657Z
@Tsuyoshi: Since **US** [contains](http://qwiki.stanford.edu/index.php/Complexity_Zoo:U#us) **coNP**, if **NP** = **coNP** then the above reasoning may work (we only use the condition that **NP** $\subseteq$ **US**). Also, the function here is the NP-machine which guesses the assignments, and the value of the function on x is the set of outputs from accepting paths of the machine. (See defn 2.2 in [HNOS96].) So as the machine does not depend on the input x, the function does not depend on the input formula.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-20T14:32:28.213Z
You are right about the definitions of **PromiseUP** and **US**. I'll correct them in the next revision, maybe together with something else, since constantly revise the same problem will disturb other users in TCS SE.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-20T15:11:56.380Z
Well, your explanation of how NP=US implies Hypothesis 1.1 does not resolve my concern (I know the definition of NPSV).  I cannot see how to output a satisfying assignment for the _given_ formula instead of outputting some different formula with a unique satisfying assignment.  But I will think a little more about it.  (Also I guess that this is kind of off topic here.)
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-09T22:45:14.120Z
@Tsuyoshi Ito: One can prove $NP=coNP$ implies Hyp. 1.1 directly, without recourse to $US$: Let $M$ be a machine for the $coNP$ language consisting of pairs $(\varphi,w)$ such that $w$ is the lex. least satisfying assignment for $\varphi$. The following $NPSV$ machine outputs satisfying assignments: on input $\varphi$, nondet. guess a witness $w$; apply $M(\varphi,w)$ and output $w$ only on accepting paths of $M$. I believe that if Hsien-Chih's argument worked, the same argument, combined iwth the HNOS result, would show that $NP=UP$ implies $PH$ collapses, which is not known.
Joshua Grochow
CC BY-SA 2.5
2011-01-10T04:58:44.047Z
@Joshua: You are right, and I found the mistake in my reasoning, which is precisely what Tsuyoshi has said. I am still reading some related material, hope that after a more complete understanding to the problem I can revise the question properly. Thank you for the proof!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-10T12:01:16.517Z
@Tayfun: sorry for asking, what is a C.C.? complexity class?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-11T13:42:34.937Z
@Tayfun: Since P $\subseteq$ UP and coUP, any complexity class separated from P works? I guess you're interested in a somewhat larger class?
Hsien-Chih Chang 張顯之
<cc.complexity-theory><complexity-classes><conditional-results><unique-solution>
Consequences of UP equals NP
Hsien-Chih Chang 張顯之
# Consequences of UP equals NP

(Asked by: username_0 on 2010-12-20)

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](https://cstheory.stackexchange.com/q/4792/1800).

---

$\mathsf{UP}$ (the unambiguous polynomial time, see [wiki](http://en.wikipedia.org/wiki/UP_(complexity)) and [the zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo:U#up) 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](http://ccc.cs.uni-duesseldorf.de/~rothe/PDF/26197.pdf) [literature](http://www.cs.rochester.edu/~lane/=companion/isolation.pdf)) 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](http://blog.computationalcomplexity.org/2003/12/does-npup.html) in 2003. And if my understanding is correct, [the result](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.8999&rep=rep1&type=pdf) 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.

**Tags:** cc.complexity-theory, complexity-classes, conditional-results, unique-solution
> **Comments:**
> **username_1**: (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.  
> **username_0**: @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](http://cstheory.stackexchange.com/q/761/1800) 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)  
> **username_0**: (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.  
> **username_1**: 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](http://dx.doi.org/10.1137/S0097539794268315).  
> **username_0**: @Tsuyoshi: Is the following reasoning correct: If **NP** = **PromiseUP**, then all problems in **NP** reduce to USAT, which is the problem containing all formulas with a unique assignment. Then, given a formula as input, we can output a unique satisfying assignment in **NP** by guessing, which satisfies the requirement of the paper [HNOS96].  
> **username_1**: First, the “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” is called US.  See [my answer to another question](http://cstheory.stackexchange.com/questions/1639/verifying-unique-solutions-of-sat/1641#1641).  (more)  
> **username_1**: (cont’d)  Second, I cannot see how the condition NP=US implies Hypothesis 1.1 in [HNOS96].  What I cannot understand is that your function (required for Hypothesis 1.1) seems to be changing the formula, but it is not allowed.  But I must be missing something simple because the introduction of [HNOS96] states that NP=coNP “clearly” implies Hypothesis 1.1 and I cannot see the reason for this either.  
> **username_1**: 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.  
> **username_0**: @Tsuyoshi: Since **US** [contains](http://qwiki.stanford.edu/index.php/Complexity_Zoo:U#us) **coNP**, if **NP** = **coNP** then the above reasoning may work (we only use the condition that **NP** $\subseteq$ **US**). Also, the function here is the NP-machine which guesses the assignments, and the value of the function on x is the set of outputs from accepting paths of the machine. (See defn 2.2 in [HNOS96].) So as the machine does not depend on the input x, the function does not depend on the input formula.  
> **username_0**: You are right about the definitions of **PromiseUP** and **US**. I'll correct them in the next revision, maybe together with something else, since constantly revise the same problem will disturb other users in TCS SE.  
> **username_1**: Well, your explanation of how NP=US implies Hypothesis 1.1 does not resolve my concern (I know the definition of NPSV).  I cannot see how to output a satisfying assignment for the _given_ formula instead of outputting some different formula with a unique satisfying assignment.  But I will think a little more about it.  (Also I guess that this is kind of off topic here.)  
> **username_2**: @Tsuyoshi Ito: One can prove $NP=coNP$ implies Hyp. 1.1 directly, without recourse to $US$: Let $M$ be a machine for the $coNP$ language consisting of pairs $(\varphi,w)$ such that $w$ is the lex. least satisfying assignment for $\varphi$. The following $NPSV$ machine outputs satisfying assignments: on input $\varphi$, nondet. guess a witness $w$; apply $M(\varphi,w)$ and output $w$ only on accepting paths of $M$. I believe that if Hsien-Chih's argument worked, the same argument, combined iwth the HNOS result, would show that $NP=UP$ implies $PH$ collapses, which is not known.  
> **username_0**: @Joshua: You are right, and I found the mistake in my reasoning, which is precisely what Tsuyoshi has said. I am still reading some related material, hope that after a more complete understanding to the problem I can revise the question properly. Thank you for the proof!  
> **username_0**: @Tayfun: sorry for asking, what is a C.C.? complexity class?  
> **username_0**: @Tayfun: Since P $\subseteq$ UP and coUP, any complexity class separated from P works? I guess you're interested in a somewhat larger class?  

---

## 1 answers

### Answer by username_3 on 2014-01-19. Score: 5

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](http://link.springer.com/article/10.1007/BF00276023), Acta Informatica,
26:363-379, 1989.

> **Comments:**
> **username_3**: This answer (http://cstheory.stackexchange.com/a/20645/495) also works here since if $UP = NP$ then the disjoint $NP$-pairs conjecture is false.  

---

