# Are there any natural hard problems where it is required that the number of solutions are always more than one?

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.

• Yes, here is NP-complete problem: Double SAT={$\phi$| formula $\phi$ has two satisfying assignments } – Mohammad Al-Turkistany Jan 29 '11 at 22:29
• 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? – Tsuyoshi Ito Jan 29 '11 at 23:17
• 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. – Tsuyoshi Ito Jan 29 '11 at 23:19
• 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". – Raphael Jan 30 '11 at 0:13
• “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. – Tsuyoshi Ito Jan 30 '11 at 0:40

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.

• @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. – Hsien-Chih Chang 張顯之 Jan 30 '11 at 5:46
• An easy observation related to the difficulty of proving UP≠NP: since P⊆UP⊆NP, showing UP≠NP also proves P≠NP. – Tsuyoshi Ito Jan 30 '11 at 7:35
• @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). – Tsuyoshi Ito Jan 30 '11 at 21:10
• @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. – Tayfun Pay Feb 1 '11 at 0:03
• @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? – Tsuyoshi Ito Feb 1 '11 at 19:43

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.

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.

• 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.. – Tayfun Pay Feb 11 '11 at 13:31
• Sure, the two solutions are isomorphic, but not identical. – Martin Schwarz Feb 11 '11 at 18:14