Following Josh Grochow's suggestion, I am converting my comment from a previous question into a new question.

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

Here $\mathsf{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: 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.

  • 6
    $\begingroup$ Related discussion here:cstheory.stackexchange.com/q/3887/1800 $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 15 '14 at 19:09
  • $\begingroup$ @Hsien-ChihChang張顯之 hm, maybe my question is duplicate. If you think so, I can flag it for deletion. $\endgroup$ – Sasho Nikolov Jan 15 '14 at 21:58
  • 4
    $\begingroup$ 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." $\endgroup$ – Joshua Grochow Jan 16 '14 at 5:54
  • 2
    $\begingroup$ 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. $\endgroup$ – Mohammad Al-Turkistany Jan 16 '14 at 13:05
  • 1
    $\begingroup$ @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}$... $\endgroup$ – Joshua Grochow Jan 16 '14 at 15:52

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.


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.