# Does “Second X is NP-complete” imply “X is NP-complete”?

"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.

• Comments are not for extended discussion; this conversation has been moved to chat. – Bjørn Kjos-Hanssen Oct 13 '19 at 4:56
• 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 Oct 15 '19 at 10:16

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.

• 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 Oct 9 '19 at 7:44
• @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 Oct 9 '19 at 7:47
• 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 Oct 9 '19 at 15:27
• 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 Oct 12 '19 at 10:56
• 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 Oct 13 '19 at 21:24

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 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). Therefore, it is plausible that Karp reductions between natural NP-complete problems can be modified to be ASP reductions.

• 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 Oct 30 '14 at 21:47
• 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 Oct 8 '19 at 10:27
• 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 Oct 8 '19 at 20:53
• 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 Oct 8 '19 at 22:51
• @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 Oct 12 '19 at 13:04