18
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 6
    $\begingroup$ Related discussion here:cstheory.stackexchange.com/q/3887/1800 $\endgroup$
    – Hsien-Chih Chang 張顯之
    Jan 15, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 15:52

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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