- Namibia Visa Overstay and Re-Entry
- Can I legally send an ex-tenant their mental health medication via Royal Mail?
- What is Wisdom?
- Why did Ralbag's commentary to Leviticus take so much longer than the other books of the Torah?
- How to count polyrhythm 3 against 4 in common time?
- Responsive Excel Web Access (or equivalent for multi file dashboard)
- How To use GetAppOnlyAuthenticatedContext when accessing Sharepoint Online Site?
- how do you share Company Holidays across regions within a single Sharepoint calendar?
- Getting GUID of a document using REST
- SharePoint Designer create or update item to another list in subsite
- Hover Panel on Content Search Web Part
- Moving from the training potty to the toilet
- Black soot on exhaust manifold 2015 Ford KA 1.2
- How to clean spilled drink from dashboard and control buttons?
- Is engine flush safe and should I do it?
- How do I save a new field value for node without saving the node?
- Is there a way to do a bundle copy from D7 to D8?
- Upgrading core to 7.6 but update.php shows unresolved dependencies
- Node urls indexed by Google
- Do not include the number in the calculations if it is below 0
Does “Second X is NP-complete” imply “X is NP-complete”?
"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 d
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.2018-06-20 19:54:25