- Backpropagation of convolutional neural network - confusion
- Why use repeated STZ instructions with the same operand on the 65c816 for the SNES (Super Nintendo)?
- Is ut ostendo sursum an accurate Latin translation of keep showing up?
- How to get transactions on only one Ethereum address?
- Truffle migrate: unknown network “development”
- How to Listen to Contract Events in Drizzle
- What does the balance mean in EtherScan?
- What are the formal specifications for the temporal reward in Casper?
- Who owns the ETH in the zero account?
- Extruder Clicking without Extrusion Problems
- Upgrade a web server based on raspberry pi 3
- Telugu typing in pantheon-terminal not rendering properly
- pixel stuck where the mouse pointer is, after trying to login with multiple user accounts
- Can I use a name which is registered in another country?
- New York State Uniform Traffic Ticket
- How to apply different Sales Tax rates to the same Membership Type - Back Office
- How to customise Shoreditch?
- Volunteer Signup - Display quantity/quantity_needed
- process_mailing processing addresses when called in UI but not CRON
- How is the music style from a lot of 70's japanese anime or tokasatsu series called?
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