11

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

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • Comments are not for extended discussion; this conversation has been moved to chat. – Bjørn Kjos-Hanssen Oct 13 '19 at 04: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

2 Answers2

10

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.

Chris Jefferson
  • 208
  • 2
  • 5
  • 4
    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 09 '19 at 07:44
  • 5
    @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 09 '19 at 07:47
  • 4
    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 09 '19 at 15:27
  • 1
    Total function problems will generally have this property, and Robert's example is as nice and simple as can be. – Rahul Savani Oct 10 '19 at 07:18
  • @ChrisJefferson The Second X problem of your example is not NP-complete. Take a non-empty subset of S which sums to zero as the given solution. Therefore, deciding the existence of a second solution is trivial (the empty set as you claim) and can not be NP-complete. Please delete your post as it does NOT answer my question. – Mohammad Al-Turkistany Oct 12 '19 at 07:50
  • 3
    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
  • There are no hard instances in your example. If you accept the empty set as a first solution then you can not reject it as a second solution. Therefore, the empty set is also the second solution. The is the consequence of using broken logic. Your Second X problem is not NP-complete . – Mohammad Al-Turkistany Oct 12 '19 at 16:10
  • Your problem does NOT require the second solution to be non-empty. Hope you see that your answer is broken. – Mohammad Al-Turkistany Oct 12 '19 at 16:16
  • @RobertAndrews I'm not interested in NP-hard problems, only NP-complete problems. – Mohammad Al-Turkistany Oct 12 '19 at 17:53
  • @MohammadAl-Turkistany I'm fairly certain the example I provided is solvable in NP, hence NP-complete. There's a slight nitpick that I stated it as a promise problem, but the problem remains NP-complete when rephrased without the promise condition. – Robert Andrews Oct 12 '19 at 19:37
  • You say "there are no hard instances of my problem, if you allow the empty set as the second solution". From a theoretical perspective, the only hard instances being those where the empty set comes first is fine. This is like saying "There are no hard instances of SAT, if do not let you have clauses longer than 2". – Chris Jefferson Oct 13 '19 at 08:43
  • @Mohammad: The problem I gave is NP-complete, as a Nash equilibrium in a bimatrix game has a polynomial-size description in the size of the game. I could have written NP-complete instead of NP-hard in my comment. – Rahul Savani Oct 13 '19 at 09:21
  • @ChrisJefferson With your logic, there is NO theoretical basis that prevents the first and second solution to be the empty set. So your example is not hard. It is trivial. If you allow the first solution to be the empty set then you must allow it to be an acceptable second solution. – Mohammad Al-Turkistany Oct 13 '19 at 12:01
  • @ChrisJefferson From a theoretical perspective, in your example, it is OK to have the first solution to be $\phi$ and the second solution to be ${ \phi }$. – Mohammad Al-Turkistany Oct 13 '19 at 12:14
  • @MohammadAl-Turkistany The definition of the second-solution problem is that given an instance and a solution, the algorithm should decide if a second solution different from the given one exists (and find one, in the search version). So in the case of subset sum, given an instance of subset sum and the empty set as a solution, the goal is to find a non-empty solution. – Sasho Nikolov Oct 13 '19 at 17:31
  • @SashoNikolov In this case, take $ \phi $ as the first solution and the second solution as $ { \phi } $ which is different from the first one. – Mohammad Al-Turkistany Oct 13 '19 at 17:42
  • @SashoNikolov If your logic allows $\phi$ to be the first solution then you can't reject ${ \phi } $ as a second solution. – Mohammad Al-Turkistany Oct 13 '19 at 17:50
  • 3
    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
  • This answer is wrong. I don't accept an empty set as a first solution (or second solution). – Mohammad Al-Turkistany Oct 14 '19 at 06:56
  • Any reasonable interpretation would interpret a solution as a non-empty set. Therefore, this contrived example is not a correct answer. – Mohammad Al-Turkistany Oct 14 '19 at 09:32
  • I don't like words like "reasonable interpretation" and "contrived". NP-completeness results are full of such things.

    Also, I think any problem which satisfies your condition is going to have this property, because if second-X is NP-complete, but X is not NP-complete, then there must be a polynomial time way of finding at least one solution, and then it be harder to find further solutions.

     – Chris Jefferson Oct 15 '19 at 10:18
0

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.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • 1
    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
  • @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 00:16
  • ASP reduction requires a polynomial time computable bijection between the solution sets of the two problems. This provides a parsimonious between ASP-complete problems. – Mohammad Al-Turkistany Jun 20 '18 at 15:06
  • 2
    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 08 '19 at 10:27
  • 2
    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 08 '19 at 20:53
  • Let me also say that the argument that natural NP-complete problems are ASP complete also seems wrong. An ASP reduction is a parsimonious reduction, but not every parsimonious reduction is an ASP reduction. The second solution problem (given one solution, find another) for NAE-SAT is obviously in P, so NAE-SAT must not be ASP-complete, because of Theorem 3.5. in the paper. – Sasho Nikolov Oct 08 '19 at 21:15
  • 4
    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 08 '19 at 22:51
  • @SashoNikolov The Second X problem of Chris's example is not NP-complete. Take a non-empty subset of S which sums to zero as the given solution. Therefore, deciding the existence of a second solution is trivial (the empty set as he claim) and can not be NP-complete. – Mohammad Al-Turkistany Oct 12 '19 at 08:03
  • 1
    @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