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

• You should find a way to avoid dummy problems like: given a graph $G$ and two nodes $s,t$, a valid solution is a path from $s$ to $t$ OR an Hamiltonian path from $s$ to $t$. A(nother)S(olution)P(roblem) is NP-complete, but the "at least one solution problem" is not NP-complete. – Marzio De Biasi Nov 29 '13 at 14:05
• You're right, in the above problem there can be multiple s-t paths, so it is not a good example. But my idea (which can be wrong :-) is: you can define an arbitrary (dummy) set with an "embedded" fixed solution like: let $A = \{ \langle G, S\rangle |$ G is a graph, S is a sequence of |V| nodes, and $S = (u_1,...,u_n)$ (the fixed solution) OR $S=(u_{i_1},...,u_{i_n})$ is an Hamiltonian cycle of G$\}$. Then you can define the problem X : given G, does exist S such that $<G,S> \in A$? "Problem X" is in P (always yes), but "Second X" is NP-complete. – Marzio De Biasi Nov 29 '13 at 22:07
• A natural problem is: given a set of integers, find a subset that adds up to zero. The empty set is always a solution, and the problem of finding another solution is famously NP-equivalent. – Colin McQuillan Nov 30 '13 at 13:51
• @Mohammad: an empty set is a perfectly good subset. The only reason the problem asks for a non-empty subset is that the empty set is always a solution. – Peter Shor Nov 30 '13 at 16:30
• @Mohammad: I don't see any natural way to exclude trivial and non-interesting artificial cases and keep the problem well-defined in terms of complexity theory. – Peter Shor Nov 30 '13 at 17:55

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.
• @domotorp That is fine since $ASP$-completeness requires p-time parsimonious reduction and all natural NP-completeness reductions are parsimonious. – Mohammad Al-Turkistany Oct 31 '14 at 0:16