If there are no accepting paths or only one accepting path, it outputs zero. And If there are more than one accepting paths it outputs Yes. I am looking for a natural problem that requires this.
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ Yes, here is NP-complete problem: Double SAT={$\phi$| formula $\phi$ has two satisfying assignments } $\endgroup$– Mohammad Al-TurkistanyJan 29, 2011 at 22:29
-
1$\begingroup$ Are you looking for a problem where each instance has at least two solutions (in particular every instance has a solution) and finding any one solution is hard? Or are you looking for a problem where each instance has either zero or at least two solutions and deciding which is the case is hard? $\endgroup$– Tsuyoshi ItoJan 29, 2011 at 23:17
-
1$\begingroup$ By the way, this is trivial (almost tautological), but SAT is in NP∖UP unless UP≠NP. Therefore, I do not think that the two sentences in your question are asking the same thing. $\endgroup$– Tsuyoshi ItoJan 29, 2011 at 23:19
-
1$\begingroup$ If $UP = NP$, then $NP \setminus UP \neq \emptyset$? I don't know what $UP$ is, but: what? Or is this a simple typo on his mission of confusion? @turkistany: if this answers the question it is not a good one since it is a trivial task to define problems like this, for appropriate choices of "natural". $\endgroup$– RaphaelJan 30, 2011 at 0:13
-
2$\begingroup$ “unless UP≠NP” in my previous comment should read either “unless UP=NP” or “if UP≠NP.” Thanks to Raphael for pointing it out. @Raphael: See UP in the Complexity Zoo for a brief explanation of UP. $\endgroup$– Tsuyoshi ItoJan 30, 2011 at 0:40
|
Show 1 more comment
3 Answers
$\begingroup$
$\endgroup$
7
In a cubic graph, the number of Hamiltonian cycles containing a given edge is even. Therefore, if a cubic graph has any Hamiltonian cycles, it has at least two. (The same has been conjectured to be true for $k$-regular graphs with $k \ge 4$ as well; I don't know the status of that conjecture.) So deciding whether a cubic graph contains a Hamiltonian cycle (which is still NP-hard) seems to meet the criteria.
However, showing that this (or any other) problem is not in UP seems difficult, since you would have to show that the multiplicity of solutions can't be eliminated by some clever non-parsimonious reduction. It's not enough to show that the obvious NP machine that solves the problem has multiple accepting paths.
-
3$\begingroup$ @mjqxxxx: As for the Second Hamiltonian Cycle Conjecture, it has been verified when $k > 22$ by Haxell, Seamone and Verstraete. See this page for a brief survey. $\endgroup$ Jan 30, 2011 at 5:46
-
$\begingroup$ An easy observation related to the difficulty of proving UP≠NP: since P⊆UP⊆NP, showing UP≠NP also proves P≠NP. $\endgroup$ Jan 30, 2011 at 7:35
-
$\begingroup$ @Geekster: (1) UP is a subclass of NP. Therefore, there is no class that includes NP but not UP. (2) Separating NP from UP is obviously at least as difficult as separating NP from P, but I cannot see the reason why “UP vs NP is as difficult as proving P vs NP problem via V.V. theorem” (assuming V.V. stands for Valiant-Vazirani). $\endgroup$ Jan 30, 2011 at 21:10
-
$\begingroup$ @Tsuyoshi: Are you sure about what you said on (1)? I do not think that is true. I think we are talking about totally different things. $\endgroup$ Feb 1, 2011 at 0:03
-
$\begingroup$ @Geekster: “Are you sure about what you said on (1)?” Yes, I am sure that what I wrote in (1) is true. See Complexity Zoo for what I mean by NP and UP. “I do not think that is true. I think we are talking about totally different things.” What are you talking about, then? $\endgroup$ Feb 1, 2011 at 19:43
$\begingroup$
$\endgroup$
0
I am also not sure if this is what you are looking for, but along the lines of mjqxxxx's answer, NAE-SAT always has an even number of solutions because the complement of any satisfying assignment is also satisfying.
answered Jan 30, 2011 at 5:43
$\begingroup$
$\endgroup$
2
Consider the NP-complete problem, for $k>2$, of $k$-coloring a graph: Either the graph is not $k$ colorable, or it has at least $k!$ distinct $k$-colorings, simply due to permutation symmetry of the $k$ colors.
For $k=2$, the problem matches your specifications: 0 or 1 accepting paths (the latter of which will never occur) will not convince the verifier, while 2 solutions (or multiples thereof) will.
-
$\begingroup$ I am not sure if this is what you mean but do you mean the fact that when k=2 and we have a solution, we can just exchange the colors and have another solution? I do not see a difference between those two solutions.. $\endgroup$ Feb 11, 2011 at 13:31
-
$\begingroup$ Sure, the two solutions are isomorphic, but not identical. $\endgroup$ Feb 11, 2011 at 18:14