Timeline for Does “Second X is NP-complete” imply “X is NP-complete”?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 12, 2019 at 13:04 | comment | added | Sasho Nikolov | @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). | |
| Oct 12, 2019 at 8:03 | comment | added | Mohammad Al-Turkistany | @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. | |
| Oct 8, 2019 at 22:51 | comment | added | Chandra Chekuri | It is a bit odd for some one to ask a question, answer it and then accept it while discussion is going on. | |
| Oct 8, 2019 at 21:15 | comment | added | Sasho Nikolov | 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. | |
| Oct 8, 2019 at 20:53 | comment | added | Sasho Nikolov | 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? | |
| Oct 8, 2019 at 10:27 | comment | added | Chris Jefferson | 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. | |
| Jun 20, 2018 at 15:34 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
added 10 characters in body
|
| Jun 20, 2018 at 15:21 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
Added a qualification to the answer.
|
| Jun 20, 2018 at 15:15 | history | edited | Mohammad Al-Turkistany | CC BY-SA 4.0 |
Added a qualification to the answer.
|
| Jun 20, 2018 at 15:06 | comment | added | Mohammad Al-Turkistany | ASP reduction requires a polynomial time computable bijection between the solution sets of the two problems. This provides a parsimonious between ASP-complete problems. | |
| Nov 9, 2014 at 2:30 | vote | accept | Mohammad Al-Turkistany | ||
| May 30, 2020 at 2:47 | |||||
| Nov 8, 2014 at 16:38 | history | edited | Mohammad Al-Turkistany | CC BY-SA 3.0 |
added 520 characters in body
|
| Oct 31, 2014 at 0:16 | comment | added | Mohammad Al-Turkistany | @domotorp That is fine since $ASP$-completeness requires p-time parsimonious reduction and all natural NP-completeness reductions are parsimonious. | |
| Oct 30, 2014 at 21:47 | comment | added | domotorp | 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. | |
| Oct 30, 2014 at 21:03 | history | answered | Mohammad Al-Turkistany | CC BY-SA 3.0 |