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

<p>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.</p>

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

CC BY-SA 4.0
2020-05-31T21:25:27.880Z
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
CC BY-SA 4.0
2020-05-31T21:31:28.557Z
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
CC BY-SA 4.0
2020-05-31T21:38:42.970Z
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
CC BY-SA 4.0
2020-05-31T22:01:40.297Z
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
CC BY-SA 4.0
2020-05-31T22:17:44.493Z
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
CC BY-SA 4.0
2020-05-31T22:19:33.867Z
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
CC BY-SA 4.0
2020-05-31T22:21:21.513Z
In the same way that we can modify Karp reductions to be parsimonious reduction that preserves the number of solutions.
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-05-31T22:25:15.387Z
"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
CC BY-SA 4.0
2020-05-31T22:31:15.687Z
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
CC BY-SA 4.0
2020-05-31T22:36:48.927Z
BTW, Do you think that your example is a counter-example to Goldreich's statement about parsimonious reductions?
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-06-01T21:13:53.657Z
@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
CC BY-SA 4.0
2020-06-03T18:06:40.277Z
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
CC BY-SA 4.0
2020-05-31T20:56:03.840Z
2020-05-31T20:56:03.840Z
Marzio De Biasi
<p><span class="math-container">$ASP$</span>-complete reductions, introduced by Ueda and Nagao, relate the hardness of computational problems in <span class="math-container">$FNP$</span>. Basically, <a href="http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf" rel="nofollow noreferrer"><span class="math-container">$ASP$</span>-reduction</a> is a polynomial time reduction between instances and a polynomial time computable bijection on solution sets. <span class="math-container">$ASP$</span>-completeness implies the <span class="math-container">$NP$</span>-completeness of the corresponding decision problem.</p>

<p>I came up with the following conjecture: There is an <span class="math-container">$ASP$</span>-reduction between any pair of (natural) <span class="math-container">$NP$</span>-complete problems. </p>

<p>In other words, every Karp reduction between <span class="math-container">$NP$</span>-complete problems can be modified by providing polynomial-time computable bijection on solution sets.</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p><strong>UPDATE</strong> For this post, <em>natural problems</em> 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 <em>natural</em> NP-complete problems surveyed by <a href="https://link.springer.com/chapter/10.1007%2F978-3-319-05446-9_2" rel="nofollow noreferrer">Allender</a>. Specifically, NP-complete problems that are either p-isomorphic to SAT or NP-creative or have universal relation.  </p>

<p>P.S. Goldreich states that "all known reductions among <strong>natural</strong> <span class="math-container">$NP$</span>-complete problems are either parsimonious or can be easily modified to be so". The above conjecture is strengthening of Goldreich's observation. ( <a href="http://books.google.com.sa/books?id=EuguvA-w5OEC&amp;pg=PA204&amp;lpg=PA204&amp;dq=natural+problem+parsimonious+reduction&amp;source=bl&amp;ots=ORhA93Hr6i&amp;sig=3Oi_F70aiaVOZ2aYlQENBteqwV4&amp;hl=en&amp;sa=X&amp;ei=dUBeVK3oHbGu7Abui4DQBQ&amp;ved=0CB0Q6AEwAA#v=onepage&amp;q=natural%20problem%20parsimonious%20reduction&amp;f=false" rel="nofollow noreferrer">Computational Complexity: A Conceptual Perspective By Oded Goldreich</a>, page 204). </p>

<p>References:</p>

<p>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.</p>

CC BY-SA 4.0
2020-05-29T19:45:56.950Z
Define “natural”.
Emil Jeřábek
CC BY-SA 4.0
2020-05-29T22:14:24.800Z
@EmilJeřábek See https://cstheory.stackexchange.com/questions/27215 and 
https://cstheory.stackexchange.com/questions/33076
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-05-29T22:28:54.737Z
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
CC BY-SA 4.0
2020-05-29T22:37:47.547Z
@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
CC BY-SA 4.0
2020-05-29T23:03:29.497Z
So you mean the (unsolved) well known [Berman–Hartmanis conjecture](https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture)?
Marzio De Biasi
CC BY-SA 4.0
2020-05-29T23:05:22.737Z
@MarzioDeBiasi NO, in BH conjecture, the bijection is between instances.
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-05-29T23:32:52.383Z
@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
CC BY-SA 4.0
2020-05-29T23:40:20.533Z
@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
CC BY-SA 4.0
2020-05-29T23:42:39.887Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/108658/discussion-between-marzio-de-biasi-and-mohammad-al-turkistany).
Marzio De Biasi
CC BY-SA 4.0
2020-05-30T03:39:52.693Z
@MarzioDeBiasi Have a look at this: https://cs.stackexchange.com/questions/77957
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-05-30T06:17:13.460Z
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
CC BY-SA 4.0
2020-05-30T12:45:20.797Z
@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
CC BY-SA 4.0
2020-05-30T14:03:15.293Z
@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
<cc.complexity-theory><np-hardness>
Conjecture about ASP reductions between NP-complete problems
Mohammad Al-Turkistany
# Conjecture about ASP reductions between NP-complete problems

(Asked by: username_0 on 2020-05-29)

$ASP$-complete reductions, introduced by Ueda and Nagao, relate the hardness of computational problems in $FNP$. Basically, [$ASP$-reduction](http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf) 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](https://link.springer.com/chapter/10.1007%2F978-3-319-05446-9_2). 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](http://books.google.com.sa/books?id=EuguvA-w5OEC&pg=PA204&lpg=PA204&dq=natural+problem+parsimonious+reduction&source=bl&ots=ORhA93Hr6i&sig=3Oi_F70aiaVOZ2aYlQENBteqwV4&hl=en&sa=X&ei=dUBeVK3oHbGu7Abui4DQBQ&ved=0CB0Q6AEwAA#v=onepage&q=natural%20problem%20parsimonious%20reduction&f=false), 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.

**Tags:** cc.complexity-theory, np-hardness
> **Comments:**
> **username_1**: Define “natural”.  
> **username_0**: @EmilJeřábek See https://cstheory.stackexchange.com/questions/27215 and  https://cstheory.stackexchange.com/questions/33076  
> **username_2**: 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.  
> **username_0**: @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.  
> **username_2**: So you mean the (unsolved) well known [Berman–Hartmanis conjecture](https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture)?  
> **username_0**: @MarzioDeBiasi NO, in BH conjecture, the bijection is between instances.  
> **username_2**: @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?  
> **username_0**: @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.  
> **username_2**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/108658/discussion-between-marzio-de-biasi-and-mohammad-al-turkistany).  
> **username_0**: @MarzioDeBiasi Have a look at this: https://cs.stackexchange.com/questions/77957  
> **username_1**: 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.  
> **username_0**: @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.  
> **username_0**: @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  

---

## 1 answers

### Answer by username_2 on 2020-05-31. Score: 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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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").  
> **username_0**: Your example also violates Goldreich's statement about parsimonious reductions. But I think it is not a valid counter-example to his conjecture.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: In the same way that we can modify Karp reductions to be parsimonious reduction that preserves the number of solutions.  
> **username_0**: "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.  
> **username_0**: 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.  
> **username_0**: BTW, Do you think that your example is a counter-example to Goldreich's statement about parsimonious reductions?  
> **username_2**: @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.  
> **username_3**: 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?  

---

