11
$\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$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Bjørn Kjos-Hanssen Oct 13 at 4:56
  • $\begingroup$ 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. $\endgroup$ – Chris Jefferson Oct 15 at 10:16
9
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ Unless you can define an "unnatural" problem, this doesn't matter. People define hundreds of variants of problems like subset sum and SAT. $\endgroup$ – Chris Jefferson Oct 9 at 7:44
  • 5
    $\begingroup$ @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. $\endgroup$ – Rahul Savani Oct 9 at 7:47
  • 4
    $\begingroup$ 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. $\endgroup$ – Robert Andrews Oct 9 at 15:27
  • 3
    $\begingroup$ 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. $\endgroup$ – Chris Jefferson Oct 12 at 10:56
  • 3
    $\begingroup$ 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 ϕ $\endgroup$ – Chris Jefferson Oct 13 at 21:24
0
$\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
  • 2
    $\begingroup$ 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. $\endgroup$ – Chris Jefferson Oct 8 at 10:27
  • 2
    $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Oct 8 at 20:53
  • 4
    $\begingroup$ It is a bit odd for some one to ask a question, answer it and then accept it while discussion is going on. $\endgroup$ – Chandra Chekuri Oct 8 at 22:51
  • 1
    $\begingroup$ @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). $\endgroup$ – Sasho Nikolov Oct 12 at 13:04

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.