17
$\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.

$\endgroup$
7
  • 6
    $\begingroup$ Related discussion here:cstheory.stackexchange.com/q/3887/1800 $\endgroup$ 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$ 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$ 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$ 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$ Jan 16, 2014 at 15:52

1 Answer 1

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.

$\endgroup$
2

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.