<p>Even, Selman, and Yacobi conjectured that there does not exist a disjoint $NP$-pair $(A, B)$ such that all separators of $(A, B)$ are $ \le_T^p $-hard for $NP$. This conjecture implies that $UP \ne NP$.</p>

<p>S. Even, A. Selman, and J. Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61:159–173, 1984.</p>

CC BY-SA 3.0
2014-01-19T01:18:09.850Z
This also works as good answer for the related post http://cstheory.stackexchange.com/questions/3887/consequences-of-up-equals-np
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-19T01:49:06.783Z
This strong conjecture also implies that $NP \ne coNP$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-19T01:13:11.550Z
2014-01-19T01:13:11.550Z
Mohammad Al-Turkistany
<p>Following Josh Grochow's suggestion, I am converting my comment from a previous <a href="https://cstheory.stackexchange.com/q/14791/4896">question</a> into a new question.</p>

<blockquote>
  <p>What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?</p>
</blockquote>

<p>Here <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#up" rel="nofollow noreferrer">$\mathsf{UP}$</a> is the class of languages recognizable by polynomial time non-deterministic Turing machines that have a unique accepting path on "yes" instances and no accepting path on "no" instances. </p>

<p>Obviously $\mathsf{UP} \subseteq \mathsf{NP}$, but why would we believe that the containment is strict? The evidence I can find is <a href="http://dl.acm.org/citation.cfm?id=322306" rel="nofollow noreferrer">oracle separation</a>: subject to a random oracle, $\mathsf{P} \subsetneq \mathsf{UP} \subsetneq \mathsf{NP}$. Also, the Complexity Zoo suggests that $\mathsf{UP}$ is not believed to have complete problems.</p>

CC BY-SA 3.0
2014-01-15T19:09:43.110Z
Related discussion here:http://cstheory.stackexchange.com/q/3887/1800
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2014-01-15T21:58:09.080Z
@Hsien-ChihChang張顯之 hm, maybe my question is duplicate. If you think so, I can flag it for deletion.
Sasho Nikolov
CC BY-SA 3.0
2014-01-16T05:54:38.693Z
I don't think this is a duplicate. I'd think that answers to the other question would count as answers to this one, but not necessarily vice versa - there could be reasons to believe $\mathsf{NP} \neq \mathsf{UP}$ that aren't of the form "If $\mathsf{NP}=\mathsf{UP}$, then some (other) bad complexity consequence happens."
Joshua Grochow
CC BY-SA 3.0
2014-01-16T05:56:33.247Z
It might be worth adding (or maybe it's too obvious to bother) that the question *assumes $\mathsf{P} \neq \mathsf{NP}$,* so any evidence that $\mathsf{NP} \neq \mathsf{UP}$ should probably be free to make that assumption as well...
Joshua Grochow
CC BY-SA 3.0
2014-01-16T06:22:39.040Z
I agree with @JoshuaGrochow; and we might attract some good answers to this question since it is now on the first page.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2014-01-16T13:05:21.627Z
The best evidence is that we have sub-exponential upper bounds on some natural **intractable** problems in UP (such as the decision versions of discrete logarithm and integer factorization) while we are not able to find such upper bound for certain NP-complete problems such as 3SAT. Such upper bound for 3SAT is impossible assuming the Exponential time hypothesis.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-01-16T15:52:22.090Z
@MohammadAl-Turkistany: But those problems are in $\mathsf{UP} \cap \mathsf{coUP}$, so if $\mathsf{NP} = \mathsf{UP}$, then they would still only be in $\mathsf{NP} \cap \mathsf{coNP}$, so wouldn't be $\mathsf{NP}$-complete unless $\mathsf{NP} = \mathsf{coNP}$...
Joshua Grochow
<cc.complexity-theory><complexity-classes><conditional-results><unique-solution>
What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?
Sasho Nikolov
# What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?

(Asked by: username_0 on 2014-01-15)

Following Josh Grochow's suggestion, I am converting my comment from a previous [question](https://cstheory.stackexchange.com/q/14791/4896) into a new question.

> What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?

Here [$\mathsf{UP}$](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#up) is the class of languages recognizable by polynomial time non-deterministic Turing machines that have a unique accepting path on "yes" instances and no accepting path on "no" instances.

Obviously $\mathsf{UP} \subseteq \mathsf{NP}$, but why would we believe that the containment is strict? The evidence I can find is [oracle separation](http://dl.acm.org/citation.cfm?id=322306): subject to a random oracle, $\mathsf{P} \subsetneq \mathsf{UP} \subsetneq \mathsf{NP}$. Also, the Complexity Zoo suggests that $\mathsf{UP}$ is not believed to have complete problems.

**Tags:** cc.complexity-theory, complexity-classes, conditional-results, unique-solution

> **Comments:**
> **username_1**: Related discussion here:http://cstheory.stackexchange.com/q/3887/1800  
> **username_0**: @Hsien-ChihChang張顯之 hm, maybe my question is duplicate. If you think so, I can flag it for deletion.  
> **username_2**: I don't think this is a duplicate. I'd think that answers to the other question would count as answers to this one, but not necessarily vice versa - there could be reasons to believe $\mathsf{NP} \neq \mathsf{UP}$ that aren't of the form "If $\mathsf{NP}=\mathsf{UP}$, then some (other) bad complexity consequence happens."  
> **username_2**: It might be worth adding (or maybe it's too obvious to bother) that the question *assumes $\mathsf{P} \neq \mathsf{NP}$,* so any evidence that $\mathsf{NP} \neq \mathsf{UP}$ should probably be free to make that assumption as well...  
> **username_1**: I agree with @JoshuaGrochow; and we might attract some good answers to this question since it is now on the first page.  
> **username_3**: The best evidence is that we have sub-exponential upper bounds on some natural **intractable** problems in UP (such as the decision versions of discrete logarithm and integer factorization) while we are not able to find such upper bound for certain NP-complete problems such as 3SAT. Such upper bound for 3SAT is impossible assuming the Exponential time hypothesis.  
> **username_2**: @MohammadAl-Turkistany: But those problems are in $\mathsf{UP} \cap \mathsf{coUP}$, so if $\mathsf{NP} = \mathsf{UP}$, then they would still only be in $\mathsf{NP} \cap \mathsf{coNP}$, so wouldn't be $\mathsf{NP}$-complete unless $\mathsf{NP} = \mathsf{coNP}$...  

---

## 1 answers

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

Even, Selman, and Yacobi conjectured that there does not exist a disjoint $NP$-pair $(A, B)$ such that all separators of $(A, B)$ are $ \le\_T^p $-hard for $NP$. This conjecture implies that $UP \ne NP$.

S. Even, A. Selman, and J. Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61:159–173, 1984.

> **Comments:**
> **username_3**: This also works as good answer for the related post http://cstheory.stackexchange.com/questions/3887/consequences-of-up-equals-np  
> **username_3**: This strong conjecture also implies that $NP \ne coNP$.  

---

