<p>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. </p>

CC BY-SA 2.5
2011-01-30T05:43:38.100Z
2011-01-30T05:43:38.100Z
Suresh Venkat
<p>Consider the NP-complete problem, for $k&gt;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. </p>

<p>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.</p>

CC BY-SA 2.5
2011-02-11T13:31:26.070Z
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
CC BY-SA 2.5
2011-02-11T18:14:29.980Z
Sure, the two solutions are isomorphic, but not identical.
Martin Schwarz
CC BY-SA 2.5
2011-02-05T15:45:47.200Z
2011-02-06T09:01:20.997Z
2011-02-06T09:01:20.997Z
Martin Schwarz
<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-01-30T05:46:38.750Z
@mjqxxxx: As for the Second Hamiltonian Cycle Conjecture, [it has been verified](http://onlinelibrary.wiley.com/doi/10.1002/jgt.20205/abstract) when $k > 22$ by Haxell, Seamone and Verstraete. See [this page](http://www.math.uiuc.edu/~west/regs/extraham.html) for a brief survey.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-30T07:35:57.693Z
An easy observation related to the difficulty of proving UP≠NP: since P⊆UP⊆NP, showing UP≠NP also proves P≠NP.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-30T21:10:28.293Z
@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
CC BY-SA 2.5
2011-02-01T00:03:48.537Z
@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
CC BY-SA 2.5
2011-02-01T19:43:18.547Z
@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
CC BY-SA 2.5
2011-02-01T22:23:22.410Z
@Tsuyoshi: Look at Suresh's answer below. As he stated when NAE-SAT has a solution, it is always at least 2. And as far as I know NAE-SAT is NP-Complete. Therefore, it is not in UP...
Tayfun Pay
CC BY-SA 2.5
2011-02-01T22:29:18.977Z
@Geekster: So what?  Your last comment has nothing to do with my comment (1).  By the way, I do not want to keep bothering mjqxxxx by this off-topic discussion.
Tsuyoshi Ito
CC BY-SA 4.0
2023-11-24T18:20:45.540Z
Unfortunately https://math.illinois.edu~west/regs/extraham.html is dead, and does not seem to have been preserved by Internet Archive :/
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-11-24T18:29:46.027Z
The conjecture that 4-regular graphs cannot have exactly one hamiltonian cycle is apparently still open as of 2019, see Goedgebeur et al., "Graphs with few Hamiltonian Cycles" https://lirias.kuleuven.be/retrieve/633716
Antoine Amarilli 'a3nm'
CC BY-SA 2.5
2011-01-30T02:50:30.407Z
2011-01-30T02:55:43.820Z
2011-01-30T02:55:43.820Z
mjqxxxx
<p>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. </p>

CC BY-SA 2.5
2011-01-29T22:29:15.100Z
Yes, here is NP-complete problem: Double SAT={$\phi$| formula $\phi$ has two satisfying assignments }
Mohammad Al-Turkistany
CC BY-SA 2.5
2011-01-29T23:17:03.170Z
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
CC BY-SA 2.5
2011-01-29T23:19:30.360Z
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
CC BY-SA 2.5
2011-01-30T00:13:24.993Z
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
CC BY-SA 2.5
2011-01-30T00:40:33.970Z
“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](http://qwiki.stanford.edu/index.php/Complexity_Zoo:U#up) in the Complexity Zoo for a brief explanation of UP.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-30T03:16:48.387Z
I think that was a typo. I revised it. I am not sure if what I am asking for is NP-UP. What do you guys think?
Tayfun Pay
<cc.complexity-theory><reference-request><counting-complexity>
Are there any natural hard problems where it is required that the number of solutions are always more than one?
Tayfun Pay
# Are there any natural hard problems where it is required that the number of solutions are always more than one?

(Asked by: username_0 on 2011-01-29)

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.

**Tags:** cc.complexity-theory, reference-request, counting-complexity
> **Comments:**
> **username_1**: Yes, here is NP-complete problem: Double SAT={$\phi$| formula $\phi$ has two satisfying assignments }  
> **username_2**: 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?  
> **username_2**: 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.  
> **username_3**: 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".  
> **username_2**: “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](http://qwiki.stanford.edu/index.php/Complexity_Zoo:U#up) in the Complexity Zoo for a brief explanation of UP.  
> **username_0**: I think that was a typo. I revised it. I am not sure if what I am asking for is NP-UP. What do you guys think?  

---

## 3 answers

### Answer by username_6 on 2011-01-30. Score: 14 | Accepted answer

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.

> **Comments:**
> **username_7**: @mjqxxxx: As for the Second Hamiltonian Cycle Conjecture, [it has been verified](http://onlinelibrary.wiley.com/doi/10.1002/jgt.20205/abstract) when $k > 22$ by Haxell, Seamone and Verstraete. See [this page](http://www.math.uiuc.edu/~west/regs/extraham.html) for a brief survey.  
> **username_2**: An easy observation related to the difficulty of proving UP≠NP: since P⊆UP⊆NP, showing UP≠NP also proves P≠NP.  
> **username_2**: @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).  
> **username_0**: @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.  
> **username_2**: @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?  
> **username_0**: @Tsuyoshi: Look at Suresh's answer below. As he stated when NAE-SAT has a solution, it is always at least 2. And as far as I know NAE-SAT is NP-Complete. Therefore, it is not in UP...  
> **username_2**: @Geekster: So what?  Your last comment has nothing to do with my comment (1).  By the way, I do not want to keep bothering mjqxxxx by this off-topic discussion.  
> **username_8**: Unfortunately https://math.illinois.edu~west/regs/extraham.html is dead, and does not seem to have been preserved by Internet Archive :/  
> **username_8**: The conjecture that 4-regular graphs cannot have exactly one hamiltonian cycle is apparently still open as of 2019, see Goedgebeur et al., "Graphs with few Hamiltonian Cycles" https://lirias.kuleuven.be/retrieve/633716  

---

### Answer by username_4 on 2011-01-30. Score: 10

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.


---

### Answer by username_5 on 2011-02-05. Score: 6

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.

> **Comments:**
> **username_0**: 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..  
> **username_5**: Sure, the two solutions are isomorphic, but not identical.  

---

