13
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Nov 29 '13 at 14:05
  • 4
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Nov 29 '13 at 22:07
  • 8
    $\begingroup$ 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. $\endgroup$ – Colin McQuillan Nov 30 '13 at 13:51
  • 7
    $\begingroup$ @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. $\endgroup$ – Peter Shor Nov 30 '13 at 16:30
  • 4
    $\begingroup$ @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. $\endgroup$ – Peter Shor Nov 30 '13 at 17:55
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – domotorp Oct 30 '14 at 21:47
  • $\begingroup$ @domotorp That is fine since $ASP$-completeness requires p-time parsimonious reduction and all natural NP-completeness reductions are parsimonious. $\endgroup$ – Mohammad Al-Turkistany Oct 31 '14 at 0:16
  • $\begingroup$ ASP reduction requires a polynomial time computable bijection between the solution sets of the two problems. This provides a parsimonious between ASP-complete problems. $\endgroup$ – Mohammad Al-Turkistany Jun 20 '18 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.