-1

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

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • 1
    Define “natural”. – Emil Jeřábek May 29 '20 at 19:45
  • @EmilJeřábek See https://cstheory.stackexchange.com/questions/27215 and https://cstheory.stackexchange.com/questions/33076 – Mohammad Al-Turkistany 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. – Marzio De Biasi 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. – Mohammad Al-Turkistany May 29 '20 at 22:37
  • So you mean the (unsolved) well known Berman–Hartmanis conjecture? – Marzio De Biasi May 29 '20 at 23:03
  • @MarzioDeBiasi NO, in BH conjecture, the bijection is between instances. – Mohammad Al-Turkistany May 29 '20 at 23:05
  • @MohammadAl-Turkistany: ok perhaps I didn't understand the question. Suppose you have an instance of SAT with only one solution (the solution set has one element), how can you 1:1 map it to the solution set of an instance of Hamiltonian Path on cubic graphs? – Marzio De Biasi May 29 '20 at 23:32
  • @MarzioDeBiasi SAT with only one solution (the solution set has one element) is USAT which is US-hard and it is not known to be NP-complete under Karp reduction. The conjecture involves two NP-complete problems. – Mohammad Al-Turkistany May 29 '20 at 23:40
  • Let us continue this discussion in chat. – Marzio De Biasi May 29 '20 at 23:42
  • @MarzioDeBiasi Have a look at this: https://cs.stackexchange.com/questions/77957 – Mohammad Al-Turkistany May 30 '20 at 03:39
  • 3
    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. – Emil Jeřábek May 30 '20 at 06:17
  • @EmilJeřábek Good point. 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. See the modified post. – Mohammad Al-Turkistany May 30 '20 at 12:45
  • @EmilJeřábek If your interested in answering the post, you can use any of the other notions of natural NP-complete problems surveyed in this paper by Allender : Allender E. (2014) Investigations Concerning the Structure of Complete Sets. In: Agrawal M., Arvind V. (eds) Perspectives in Computational Complexity. Progress in Computer Science and Applied Logic, vol 26. Birkhäuser, Cham – Mohammad Al-Turkistany May 30 '20 at 14:03

1 Answers1

2

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.

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • 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. – Mohammad Al-Turkistany May 31 '20 at 21:25
  • 1
    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"). – Marzio De Biasi May 31 '20 at 21:31
  • Your example also violates Goldreich's statement about parsimonious reductions. But I think it is not a valid counter-example to his conjecture. – Mohammad Al-Turkistany May 31 '20 at 21:38
  • 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. – Mohammad Al-Turkistany May 31 '20 at 22:01
  • I am not interested in ASP-completeness, this is the conjecture: Every Karp reduction between NP-complete problems can be modified by providing polynomial-time computable bijection on solution sets. So, my conjecture is a stronger form of Goldreich's statement. Instead of asking for parsimonious reduction, we ask for a Karp reduction which additionally provides a P-time bijection between solutions sets. – Mohammad Al-Turkistany May 31 '20 at 22:17
  • Sorry but I stil don't understand. What do you mean with "every Karp reduction can be modified"? A Karp reduction is between instances (in this case between two "natural" NP-complete problems), how can you "modify it providing a bijection on solution sets"?What is the result of the modified Karp reduction? Can you give an example of a Karp reduction that is/can be "modified by a poly-time computable bijection on solution sets"? How can you "modify a Karp reduction to be an ASP reduction"?An ASP reduction is composed by 2 functions, one between the instances and one between the solution sets. – Marzio De Biasi May 31 '20 at 22:19
  • In the same way that we can modify Karp reductions to be parsimonious reduction that preserves the number of solutions. – Mohammad Al-Turkistany May 31 '20 at 22:21
  • "An ASP reduction is composed by 2 functions, one between the instances and one between the solution sets", exactly. The modified reduction provide these two P-time functions. – Mohammad Al-Turkistany May 31 '20 at 22:25
  • You can think of the conjecture as an attempt to combine both the Isomorphism conjecture of Berman and Hartmanis and Goldreich's conjecture about parsimonious reductions. – Mohammad Al-Turkistany May 31 '20 at 22:31
  • BTW, Do you think that your example is a counter-example to Goldreich's statement about parsimonious reductions? – Mohammad Al-Turkistany May 31 '20 at 22:36
  • @MohammadAl-Turkistany: a reduction to Hamiltonian circuit on cubic graphs is weakly parsimonious; and it is easy to recover the number of solutions (in polytime) of the original problrm (just multiply by a constant if I remember well). But in the context of ASP reductions, if you have one solution of the first problem, it's hard to find a second one, but it's easy to find another Hamiltonian cycle on cubic graphs. – Marzio De Biasi Jun 01 '20 at 21:13
  • 1
    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? – Neal Young Jun 03 '20 at 18:06