Latest update

# Does “Second X is NP-complete” imply “X is NP-complete”?

2018-06-20 18:55:17

"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