# Conjecture about ASP reductions between NP-complete problems

$$ASP$$-complete reductions, introduced by Ueda and Nagao, relate the hardness of computational problems in $$FNP$$. Basically, $$ASP$$-reduction is a polynomial time reduction between instances and a polynomial time computable bijection on solution sets. $$ASP$$-completeness implies the $$NP$$-completeness of the corresponding decision problem.

I came up with the following conjecture: There is an $$ASP$$-reduction between any pair of (natural) $$NP$$-complete problems.

In other words, every Karp reduction between $$NP$$-complete problems can be modified by providing polynomial-time computable bijection on solution sets.

Is this a known conjecture? Is there any counterexample? What are the complexity-theoretic consequences? Does it have any implication on the Isomorphism Conjecture of Berman and Hartmanis?

UPDATE For this post, natural problems are the NP-complete problems listed in Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (to address Emil's comment). Also, I accept other more general notions of natural NP-complete problems surveyed by Allender. Specifically, NP-complete problems that are either p-isomorphic to SAT or NP-creative or have universal relation.

P.S. Goldreich states that "all known reductions among natural $$NP$$-complete problems are either parsimonious or can be easily modified to be so". The above conjecture is strengthening of Goldreich's observation. ( Computational Complexity: A Conceptual Perspective By Oded Goldreich, page 204).

References:

N. Ueda and T. Nagao. NP-completeness results for NONOGRAM via parsimonious reductions. Technical Report TR96-0008, Department of Computer Science, Tokyo Institute of Technology, 1996.

• Define “natural”. May 29 '20 at 19:45
• May 29 '20 at 22:14
• You should check the notion of ASP-completeness and NP-completeness of n-ASP (both defined in Takayuki Yato "Complexity and Completeness of Finding Another Solution and its Application to Puzzles"). Furthermore finding an Hamiltonian cycle in cubic graphs is NP-complete, but the corresponding function problem is not ASP-complete (because a cubic graph with a Hamiltonian circuit always has another); so your conjecture seems false. May 29 '20 at 22:28
• @MarzioDeBiasi The conjecture is not about ASP-completeness. It is about restricting Karp reduction to a reduction that requires polynomial time computable bijection on solution sets. May 29 '20 at 22:37
• Neither of your links give a definition of natural. Without it, the thing you wrote is no “conjecture”. A conjecture is an unambiguous mathematical statement that can be, in principle, proved or disproved. Putting in weasel words like “natural” makes a mockery of it. There is no way to falsify this “conjecture” because for any proposed counterexample, you will just arbitrarily decide that it is not natural. Naturally, here is a counterconjecture: there is no natural theorem about a natural class of computational problems that only works when restricted to natural problems. May 30 '20 at 6:17

• Similarly consider NAE-3SAT. Putting aside the question of whether it is natural, every instance of NAE-3SAT has an even number of solutions (because the logical complement of any NAE-satisfying assignment is also an NAE-satisfying assignment). So, because SAT has instances with an odd number of solutions, there is no reduction f from SAT to NAE-3SAT such that for every SAT instance $\phi$, there is a bijection between solutions for $\phi$ and solutions for $f(\phi)$. (Take $\phi$ to be, for example, the SAT instance $\phi=x_1$, which has exactly one solution.) Am I missing something? Jun 3 '20 at 18:06