-1
$\begingroup$

$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.

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ Define “natural”. $\endgroup$
    – Emil Jeřábek
    Commented May 29, 2020 at 19:45
  • $\begingroup$ @EmilJeřábek See cstheory.stackexchange.com/questions/27215 and cstheory.stackexchange.com/questions/33076 $\endgroup$
    – Mohammad Al-Turkistany
    Commented May 29, 2020 at 22:14
  • $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    Commented May 29, 2020 at 22:28
  • $\begingroup$ @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. $\endgroup$
    – Mohammad Al-Turkistany
    Commented May 29, 2020 at 22:37
  • 3
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented May 30, 2020 at 6:17

1 Answer 1

Reset to default
2
$\begingroup$

As far as Hamiltonian circuit on cubic graphs is natural your conjecture "There is an ASP-reduction between any pair of (natural) NP-complete problems" is false.

There is no ASP-reduction from SAT (another natural problem) to Hamiltonian circuit on cubic graphs, because every cubic graph that has an Hamiltonian cycle has another Hamiltonian cycle different than the first one, see C. H. Papadimitriou, Computational Complexity.

Another way to state it: 1-ASP (one another solution) Hamiltonian circuit on cubic graphs is not NP-complete, so the corresponding function problem cannot be ASP-complete.

Improve this answer
$\endgroup$
12
  • $\begingroup$ This arises because you are reducing from the most general form of SAT to restricted Hamiltonian circuit problem. This should disappear if the reduction from restricted NP-complete problem to another restricted problem. For instance, reduce Cubic 1-in-3 SAT to Hamiltonian circuit on cubic graphs. $\endgroup$
    – Mohammad Al-Turkistany
    Commented May 31, 2020 at 21:25
  • 1
    $\begingroup$ Mmmm ... you asked for "any pair", but it seems that you require not only that problems are natural, but even if they are natural they are ok only if they satisfy your conjecture ... (a sort of "loop"). $\endgroup$
    – Marzio De Biasi
    Commented May 31, 2020 at 21:31
  • $\begingroup$ Your example also violates Goldreich's statement about parsimonious reductions. But I think it is not a valid counter-example to his conjecture. $\endgroup$
    – Mohammad Al-Turkistany
    Commented May 31, 2020 at 21:38
  • $\begingroup$ The point is that if you restrict one side of the reduction, you can restrict the other side and modify the Karp reduction to be an ASP reduction. $\endgroup$
    – Mohammad Al-Turkistany
    Commented May 31, 2020 at 22:01
  • 1
    $\begingroup$ 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? $\endgroup$
    – Neal Young
    Commented Jun 3, 2020 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.