Skip to main content
1 of 10

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:

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