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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Oct 13, 2019 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
    Commented Oct 15, 2019 at 10:16

2 Answers 2

Reset to default
10
$\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.

Improve this answer
$\endgroup$
21
  • 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
    Commented Oct 9, 2019 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
    Commented Oct 9, 2019 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
    Commented Oct 9, 2019 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
    Commented Oct 12, 2019 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
    Commented Oct 13, 2019 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.

Improve this answer
$\endgroup$
9
  • 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
    Commented Oct 30, 2014 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
    Commented Oct 8, 2019 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
    Commented Oct 8, 2019 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
    Commented Oct 8, 2019 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
    Commented Oct 12, 2019 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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