<p>No,</p>

<p>Consider the problem "Find a subset of a set of integers S which sums to 0".</p>

<p>This problem is trivial, as one can return the empty set.</p>

<p>However, finding a second solution after returning the empty set is the well-known subset sum problem, which is known to be NP-complete.</p>

CC BY-SA 4.0
2019-10-09T07:44:01.337Z
Unless you can define an "unnatural" problem, this doesn't matter. People define hundreds of variants of problems like subset sum and SAT.
Chris Jefferson
CC BY-SA 4.0
2019-10-09T07:47:12.237Z
@Mohammad: Here is another counter-example; I leave it to you to decide if it is natural or not: A bimatrix game always has at least one Nash equilibrium and it is NP-hard to decide if a bimatrix game has more than one Nash equilibrium [Gilboa and Zemel, GEB 1989]. The construction takes a SAT formula f and produces a game with a certain Nash equilibrium of known form that always exists, such that the game has a second equilibrium iff the formula f is satisfiable.
Rahul Savani
CC BY-SA 4.0
2019-10-09T15:27:38.567Z
Here is another counter-example, the one-dimensional version of Sperner's lemma, which is similar in spirit to the one Rahul provides. Given a Boolean circuit computing a function $f : \{0,1,2,\ldots,2^n-1\} \to \{0,1\}$ (the input is provided in binary) with the promise that $f(0) = 0$ and $f(2^n-1)=1$, find a number $k$ such that $f(k) = 0$ and $f(k+1) = 1$. Such a number always exists and is easy to find via binary search, but it is NP-hard to decide if there is more than one such position where this occurs.
Robert Andrews
CC BY-SA 4.0
2019-10-10T07:18:54.967Z
Total function problems will generally have this property, and Robert's example is as nice and simple as can be.
Rahul Savani
CC BY-SA 4.0
2019-10-12T07:50:45.243Z
@ChrisJefferson The Second X problem of your example is not NP-complete. Take a non-empty subset of S which sums to zero as the given solution. Therefore, deciding the existence of a second solution is trivial (the empty set as you claim) and can not be NP-complete. Please delete your post as it does NOT answer my question.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-12T10:56:37.597Z
NP complete does not mean that all instances are hard, just some are. There are many trivial instances of subset sum (all problems which contain 1 and - 1 for example) and many easy SAT problems (2 SAT for example), but SAT as a whole is still NP-complete.
Chris Jefferson
CC BY-SA 4.0
2019-10-12T16:10:24.730Z
There are no hard instances in your example. If you accept the empty set as a first solution then you can not reject it as a second solution. Therefore, the empty set is also the second solution. The is the consequence of using broken logic. Your Second X problem is not NP-complete .
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-12T16:16:26.440Z
Your problem does NOT require the second solution to be non-empty. Hope you see that your answer is broken.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-12T17:53:49.710Z
@RobertAndrews I'm not interested in NP-hard problems, only NP-complete problems.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-12T19:37:40.453Z
@MohammadAl-Turkistany I'm fairly certain the example I provided is solvable in NP, hence NP-complete. There's a slight nitpick that I stated it as a promise problem, but the problem remains NP-complete when rephrased without the promise condition.
Robert Andrews
CC BY-SA 4.0
2019-10-13T08:43:53.883Z
You say "there are no hard instances of my problem, if you allow the empty set as the second solution". From a theoretical perspective, the only hard instances being those where the empty set comes first is fine. This is like saying "There are no hard instances of SAT, if do not let you have clauses longer than 2".
Chris Jefferson
CC BY-SA 4.0
2019-10-13T09:21:52.863Z
@Mohammad: The problem I gave is NP-complete, as a Nash equilibrium in a bimatrix game has a polynomial-size description in the size of the game. I could have written NP-complete instead of NP-hard in my comment.
Rahul Savani
CC BY-SA 4.0
2019-10-13T12:01:26.333Z
@ChrisJefferson With your logic, there is NO theoretical basis that prevents the first and second solution to be the empty set. So your example is not hard. It is trivial. If you allow the first solution to be the empty set then you must allow it to be an acceptable second solution.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-13T12:14:40.320Z
@ChrisJefferson From a theoretical perspective, in your example, it is OK to have the first solution to be $\phi$ and the second solution to be $\{ \phi \}$.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-13T17:31:51.793Z
@MohammadAl-Turkistany The definition of the second-solution problem is that given an instance and a solution, the algorithm should decide if a second solution *different* from the given one exists (and find one, in the search version). So in the case of subset sum, given an instance of subset sum and the empty set as a solution, the goal is to find a non-empty solution.
Sasho Nikolov
CC BY-SA 4.0
2019-10-13T17:42:23.450Z
@SashoNikolov In this case, take $ \phi $ as the first solution and the second solution as $ \{ \phi \} $ which is different from the first one.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-13T17:50:05.587Z
@SashoNikolov If your logic allows $\phi$  to be the first solution then you can't reject $\{ \phi \} $ as a second solution.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-13T21:24:33.810Z
The answer must be a subset of the set of integers S. {} is a subset of S as the empty set is a subset of all sets. {ϕ} is not a subset of S, as S does not contain ϕ
Chris Jefferson
CC BY-SA 4.0
2019-10-14T06:56:45.767Z
This answer is wrong. I don't accept an empty set as a first solution (or second solution).
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-14T09:32:47.397Z
Any reasonable interpretation would interpret a solution as a non-empty set. Therefore, this contrived example is not a correct answer.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-15T10:18:02.583Z
I don't like words like "reasonable interpretation" and "contrived". NP-completeness results are full of such things.

Also, I think any problem which satisfies your condition is going to have this property, because if second-X is NP-complete, but X is not NP-complete, then there must be a polynomial time way of finding at least one solution, and then it be harder to find further solutions.
Chris Jefferson
CC BY-SA 4.0
2019-10-08T10:31:05.790Z
2019-10-08T10:31:05.790Z
Chris Jefferson
<p>The answer is yes (if ASP reduction is used instead of Karp reduction). ASP reduction requires a polynomial time computable bijection between the solution sets of the two problems. This provides a parsimonious reduction between ASP-complete problems. <a href="http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf" rel="nofollow noreferrer">Yato and Seta</a> state that $ASP$-completeness imply $NP$-completeness (Page 2, second paragraph). Another solution problem (ASP) is exactly what I call Second X problem.</p>

<p>Oded Goldreich states the fact that "all known reductions among <strong>natural</strong> $NP$-complete problems are either parsimonious or can be easily modified to be so". ( <a href="http://books.google.com.sa/books?id=EuguvA-w5OEC&amp;pg=PA204&amp;lpg=PA204&amp;dq=natural+problem+parsimonious+reduction&amp;source=bl&amp;ots=ORhA93Hr6i&amp;sig=3Oi_F70aiaVOZ2aYlQENBteqwV4&amp;hl=en&amp;sa=X&amp;ei=dUBeVK3oHbGu7Abui4DQBQ&amp;ved=0CB0Q6AEwAA#v=onepage&amp;q=natural%20problem%20parsimonious%20reduction&amp;f=false" rel="nofollow noreferrer">Computational Complexity: A Conceptual Perspective By Oded Goldreich</a>). Therefore, it is plausible that Karp reductions between <em>natural</em> NP-complete problems can be modified to be ASP reductions.</p>

CC BY-SA 3.0
2014-10-30T21:47:49.240Z
Your problem was whether NP-completeness of second solution implies NP-completeness. What they show is weaker, they require ASP-completeness, as NP-completeness is not enough, as pointed out in the comments to your question.
domotorp
CC BY-SA 3.0
2014-10-31T00:16:55.267Z
@domotorp That is fine since $ASP$-completeness requires p-time parsimonious reduction and all natural NP-completeness reductions are parsimonious.
Mohammad Al-Turkistany
CC BY-SA 4.0
2018-06-20T15:06:07.690Z
ASP reduction requires a polynomial time computable bijection between the solution sets of the two problems. This provides a parsimonious between ASP-complete problems.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-08T10:27:49.803Z
If anyone reads this, this answer is wrong. It is easy to produce a problem where Second X is NP-complete, but X is not NP-complete.

For example (as discussed in the comments above), the problem of finding a subset of a set of integers which sums to 0 is Second X NP-complete, because it is NP-complete once we reject the easy first solution of the empty set.
Chris Jefferson
CC BY-SA 4.0
2019-10-08T20:53:20.850Z
This answer doesn't make sense to me. The paper shows that ASP completeness of a problem $\Pi$ implies that the Second-Solution problem $\Pi_{[2]}$ for $\Pi$ is NP-complete. Mohammad argues that natural NP-complete problems should be ASP complete. So this would mean that for natural NP-complete problems $\Pi$, the problem $\Pi_{[2]}$ is NP-complete. But the original question asks for the converse: it asks whether hardness of $\Pi_{[2]}$ implies hardness of $\Pi$. So, I am pretty sure this answer got the logic backwards. Did I miss something?
Sasho Nikolov
CC BY-SA 4.0
2019-10-08T21:15:23.243Z
Let me also say that the argument that natural NP-complete problems are ASP complete also seems wrong. An ASP reduction is a parsimonious reduction, but not every parsimonious reduction is an ASP reduction. The second solution problem (given one solution, find another) for NAE-SAT is obviously in P, so NAE-SAT must not be ASP-complete, because of Theorem 3.5. in the paper.
Sasho Nikolov
CC BY-SA 4.0
2019-10-08T22:51:49.887Z
It is a bit odd for some one to ask a question, answer it and then accept it while discussion is going on.
Chandra Chekuri
CC BY-SA 4.0
2019-10-12T08:03:13.507Z
@SashoNikolov The Second X problem of Chris's example is not NP-complete. Take a non-empty subset of S which sums to zero as the given solution. Therefore, deciding the existence of a second solution is trivial (the empty set as he claim) and can not be NP-complete.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-10-12T13:04:42.740Z
@MohammadAl-Turkistany My comment was saying that your answer seems to have gotten the logic backwards, and does not answer your own question. I didn't say anything about Chris's example (which to me looks fine, but I don't want to get into that argument in the comments).
Sasho Nikolov
CC BY-SA 4.0
2014-10-30T21:03:33.220Z
2018-06-20T15:34:30.983Z
2018-06-20T15:34:30.983Z
Mohammad Al-Turkistany
<p>"Second $X$" problem is the problem of deciding the existence of another solution different from some given solution for problem instance. </p>

<p>For some $NP$-complete problems, the second solution version is $NP$-complete (deciding the existence of another solution for the partial Latin square completion problem) while for others it is either trivial (Second NAE SAT) or it can not be $NP$-complete (Second Hamiltonian cycle in cubic graphs) under widely believed complexity conjecture. I am interested in the opposite direction. </p>

<p>We assume a natural $NP$ problem $X$ where there is <strong>natural</strong> efficient verifier that verifies a natural <strong>interesting</strong> relation $(x, c)$ where $x$ is an input instance and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier and it does not have any knowledge of any correct witness ( both examples in the comments are solutions by definition).  </p>

<blockquote>
  <p>Does “Second $X$ is NP-complete” imply “$X$ is NP-complete” for all "natural" problems $X$?</p>
</blockquote>

<p>In other words, <strong>Are there any "natural" problem $X$ where this implication fails?</strong>. Or equivalently,</p>

<blockquote>
  <p>Is there any "natural" problem $X$ in $NP$ and not known to be $NP$-complete but its Second $X$ problem is $NP$-complete?</p>
</blockquote>

<p><strong>EDIT</strong>: Thanks to Marzio's comments, I am not interested in contrived counter-examples. I am only interested in natural and interesting counter-examples for NP-complete problems $X$ similar to the ones above. An acceptable answer is either a proof of the above implication or a counter-example "Second X problem" which is defined for natural, interesting, and well known $NP$ problem $X$.</p>

<p><strong>EDIT 2</strong>: Thanks to the fruitful discussion with David Richerby, I have edited the question to emphasis that my interest is only in natural problems $X$.</p>

<p><strong>EDIT 3</strong>: Motivation: First, the existence of such implication may simplify the $NP$-completeness proofs of many $NP$ problems. Secondly, the existence of the implication links the complexity of deciding the uniqueness of solution to the problem of deciding existence of a solution for $NP$ problems.</p>

CC BY-SA 4.0
2019-10-13T04:56:49.900Z
Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/99832/discussion-on-question-by-mohammad-al-turkistany-does-second-x-is-np-complete).
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2019-10-15T10:16:07.353Z
Your EDIT 3 and EDIT 1 don't seem to line up. If you want this to be a general result, useful for simplifying NP-completeness proofs, you can't also say you only want "non-contrived" counter-examples. Also, it would be useful to have a  definition of "natural/interesting", which wasn't based on personal opinion.
Chris Jefferson
<cc.complexity-theory><unique-solution>
Does “Second X is NP-complete” imply “X is NP-complete”?
Mohammad Al-Turkistany
# Does “Second X is NP-complete” imply “X is NP-complete”?

(Asked by: username_0 on 2013-11-29)

"Second $X$" problem is the problem of deciding the existence of another solution different from some given solution for problem instance.

For some $NP$-complete problems, the second solution version is $NP$-complete (deciding the existence of another solution for the partial Latin square completion problem) while for others it is either trivial (Second NAE SAT) or it can not be $NP$-complete (Second Hamiltonian cycle in cubic graphs) under widely believed complexity conjecture. I am interested in the opposite direction.

We assume a natural $NP$ problem $X$ where there is **natural** efficient verifier that verifies a natural **interesting** relation $(x, c)$ where $x$ is an input instance and $c$ is a short witness of membership of $x$ in $X$. All witnesses are indistinguishable to the verifier. The validity of witnesses must be decided by running the natural verifier and it does not have any knowledge of any correct witness ( both examples in the comments are solutions by definition).

> Does “Second $X$ is NP-complete” imply “$X$ is NP-complete” for all "natural" problems $X$?

In other words, **Are there any "natural" problem $X$ where this implication fails?**. Or equivalently,

> Is there any "natural" problem $X$ in $NP$ and not known to be $NP$-complete but its Second $X$ problem is $NP$-complete?

**EDIT**: Thanks to Marzio's comments, I am not interested in contrived counter-examples. I am only interested in natural and interesting counter-examples for NP-complete problems $X$ similar to the ones above. An acceptable answer is either a proof of the above implication or a counter-example "Second X problem" which is defined for natural, interesting, and well known $NP$ problem $X$.

**EDIT 2**: Thanks to the fruitful discussion with David Richerby, I have edited the question to emphasis that my interest is only in natural problems $X$.

**EDIT 3**: Motivation: First, the existence of such implication may simplify the $NP$-completeness proofs of many $NP$ problems. Secondly, the existence of the implication links the complexity of deciding the uniqueness of solution to the problem of deciding existence of a solution for $NP$ problems.

**Tags:** cc.complexity-theory, unique-solution

> **Comments:**
> **username_1**: Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/99832/discussion-on-question-by-mohammad-al-turkistany-does-second-x-is-np-complete).  
> **username_2**: Your EDIT 3 and EDIT 1 don't seem to line up. If you want this to be a general result, useful for simplifying NP-completeness proofs, you can't also say you only want "non-contrived" counter-examples. Also, it would be useful to have a  definition of "natural/interesting", which wasn't based on personal opinion.  

---

## 2 answers

### Answer by username_2 on 2019-10-08. Score: 10

No,

Consider the problem "Find a subset of a set of integers S which sums to 0".

This problem is trivial, as one can return the empty set.

However, finding a second solution after returning the empty set is the well-known subset sum problem, which is known to be NP-complete.

> **Comments:**
> **username_2**: Unless you can define an "unnatural" problem, this doesn't matter. People define hundreds of variants of problems like subset sum and SAT.  
> **username_3**: @Mohammad: Here is another counter-example; I leave it to you to decide if it is natural or not: A bimatrix game always has at least one Nash equilibrium and it is NP-hard to decide if a bimatrix game has more than one Nash equilibrium [Gilboa and Zemel, GEB 1989]. The construction takes a SAT formula f and produces a game with a certain Nash equilibrium of known form that always exists, such that the game has a second equilibrium iff the formula f is satisfiable.  
> **username_4**: Here is another counter-example, the one-dimensional version of Sperner's lemma, which is similar in spirit to the one Rahul provides. Given a Boolean circuit computing a function $f : \{0,1,2,\ldots,2^n-1\} \to \{0,1\}$ (the input is provided in binary) with the promise that $f(0) = 0$ and $f(2^n-1)=1$, find a number $k$ such that $f(k) = 0$ and $f(k+1) = 1$. Such a number always exists and is easy to find via binary search, but it is NP-hard to decide if there is more than one such position where this occurs.  
> **username_3**: Total function problems will generally have this property, and Robert's example is as nice and simple as can be.  
> **username_0**: @ChrisJefferson The Second X problem of your example is not NP-complete. Take a non-empty subset of S which sums to zero as the given solution. Therefore, deciding the existence of a second solution is trivial (the empty set as you claim) and can not be NP-complete. Please delete your post as it does NOT answer my question.  
> **username_2**: NP complete does not mean that all instances are hard, just some are. There are many trivial instances of subset sum (all problems which contain 1 and - 1 for example) and many easy SAT problems (2 SAT for example), but SAT as a whole is still NP-complete.  
> **username_0**: There are no hard instances in your example. If you accept the empty set as a first solution then you can not reject it as a second solution. Therefore, the empty set is also the second solution. The is the consequence of using broken logic. Your Second X problem is not NP-complete .  
> **username_0**: Your problem does NOT require the second solution to be non-empty. Hope you see that your answer is broken.  
> **username_0**: @RobertAndrews I'm not interested in NP-hard problems, only NP-complete problems.  
> **username_4**: @MohammadAl-Turkistany I'm fairly certain the example I provided is solvable in NP, hence NP-complete. There's a slight nitpick that I stated it as a promise problem, but the problem remains NP-complete when rephrased without the promise condition.  
> **username_2**: You say "there are no hard instances of my problem, if you allow the empty set as the second solution". From a theoretical perspective, the only hard instances being those where the empty set comes first is fine. This is like saying "There are no hard instances of SAT, if do not let you have clauses longer than 2".  
> **username_3**: @Mohammad: The problem I gave is NP-complete, as a Nash equilibrium in a bimatrix game has a polynomial-size description in the size of the game. I could have written NP-complete instead of NP-hard in my comment.  
> **username_0**: @ChrisJefferson With your logic, there is NO theoretical basis that prevents the first and second solution to be the empty set. So your example is not hard. It is trivial. If you allow the first solution to be the empty set then you must allow it to be an acceptable second solution.  
> **username_0**: @ChrisJefferson From a theoretical perspective, in your example, it is OK to have the first solution to be $\phi$ and the second solution to be $\{ \phi \}$.  
> **username_5**: @MohammadAl-Turkistany The definition of the second-solution problem is that given an instance and a solution, the algorithm should decide if a second solution *different* from the given one exists (and find one, in the search version). So in the case of subset sum, given an instance of subset sum and the empty set as a solution, the goal is to find a non-empty solution.  
> **username_0**: @SashoNikolov In this case, take $ \phi $ as the first solution and the second solution as $ \{ \phi \} $ which is different from the first one.  
> **username_0**: @SashoNikolov If your logic allows $\phi$  to be the first solution then you can't reject $\{ \phi \} $ as a second solution.  
> **username_2**: The answer must be a subset of the set of integers S. {} is a subset of S as the empty set is a subset of all sets. {ϕ} is not a subset of S, as S does not contain ϕ  
> **username_0**: This answer is wrong. I don't accept an empty set as a first solution (or second solution).  
> **username_0**: Any reasonable interpretation would interpret a solution as a non-empty set. Therefore, this contrived example is not a correct answer.  
> **username_2**: I don't like words like "reasonable interpretation" and "contrived". NP-completeness results are full of such things.  Also, I think any problem which satisfies your condition is going to have this property, because if second-X is NP-complete, but X is not NP-complete, then there must be a polynomial time way of finding at least one solution, and then it be harder to find further solutions.  

---

### Answer by username_0 on 2014-10-30. Score: 0

The answer is yes (if ASP reduction is used instead of Karp reduction). ASP reduction requires a polynomial time computable bijection between the solution sets of the two problems. This provides a parsimonious reduction between ASP-complete problems. [Yato and Seta](http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf) state that $ASP$-completeness imply $NP$-completeness (Page 2, second paragraph). Another solution problem (ASP) is exactly what I call Second X problem.

Oded Goldreich states the fact that "all known reductions among **natural** $NP$-complete problems are either parsimonious or can be easily modified to be so". ( [Computational Complexity: A Conceptual Perspective By Oded Goldreich](http://books.google.com.sa/books?id=EuguvA-w5OEC&pg=PA204&lpg=PA204&dq=natural+problem+parsimonious+reduction&source=bl&ots=ORhA93Hr6i&sig=3Oi_F70aiaVOZ2aYlQENBteqwV4&hl=en&sa=X&ei=dUBeVK3oHbGu7Abui4DQBQ&ved=0CB0Q6AEwAA#v=onepage&q=natural%20problem%20parsimonious%20reduction&f=false)). Therefore, it is plausible that Karp reductions between *natural* NP-complete problems can be modified to be ASP reductions.

> **Comments:**
> **username_6**: Your problem was whether NP-completeness of second solution implies NP-completeness. What they show is weaker, they require ASP-completeness, as NP-completeness is not enough, as pointed out in the comments to your question.  
> **username_0**: @username_6 That is fine since $ASP$-completeness requires p-time parsimonious reduction and all natural NP-completeness reductions are parsimonious.  
> **username_0**: ASP reduction requires a polynomial time computable bijection between the solution sets of the two problems. This provides a parsimonious between ASP-complete problems.  
> **username_2**: If anyone reads this, this answer is wrong. It is easy to produce a problem where Second X is NP-complete, but X is not NP-complete.  For example (as discussed in the comments above), the problem of finding a subset of a set of integers which sums to 0 is Second X NP-complete, because it is NP-complete once we reject the easy first solution of the empty set.  
> **username_5**: This answer doesn't make sense to me. The paper shows that ASP completeness of a problem $\Pi$ implies that the Second-Solution problem $\Pi_{[2]}$ for $\Pi$ is NP-complete. Mohammad argues that natural NP-complete problems should be ASP complete. So this would mean that for natural NP-complete problems $\Pi$, the problem $\Pi_{[2]}$ is NP-complete. But the original question asks for the converse: it asks whether hardness of $\Pi_{[2]}$ implies hardness of $\Pi$. So, I am pretty sure this answer got the logic backwards. Did I miss something?  
> **username_5**: Let me also say that the argument that natural NP-complete problems are ASP complete also seems wrong. An ASP reduction is a parsimonious reduction, but not every parsimonious reduction is an ASP reduction. The second solution problem (given one solution, find another) for NAE-SAT is obviously in P, so NAE-SAT must not be ASP-complete, because of Theorem 3.5. in the paper.  
> **username_7**: It is a bit odd for some one to ask a question, answer it and then accept it while discussion is going on.  
> **username_0**: @SashoNikolov The Second X problem of Chris's example is not NP-complete. Take a non-empty subset of S which sums to zero as the given solution. Therefore, deciding the existence of a second solution is trivial (the empty set as he claim) and can not be NP-complete.  
> **username_5**: @MohammadAl-Turkistany My comment was saying that your answer seems to have gotten the logic backwards, and does not answer your own question. I didn't say anything about Chris's example (which to me looks fine, but I don't want to get into that argument in the comments).  

---

