<p><em>Great</em> question! I have also had thoughts along similar lines, but not found anything in the literature that fully answers all of these questions. However, for this part of your question, I think a satisfactory answer is given by Berman &amp; Hartmanis:</p>

<blockquote>
  <p>what prevents us from adding some (polynomial amount of) structure to our NP-Complete problems so that reductions from one NP-Complete problem to another converge in size?</p>
</blockquote>

<p>In some sense, nothing: Berman &amp; Hartmanis showed that if two languages have one-to-one, polynomial-time invertible, length-increasing reductions between them in both directions, then the languages are p-isomorphic. (Here a one-to-one function $f$ is poly-time invertible if there is a poly-time function $g$ such that $g(f(x)) = x$ for all $x$, and $g(y)=\bot$ if $y$ is not in the image of $f$.) Two languages being p-isomorphic basically just means that one is a re-encoding of the other, and thus preserves the "structure" of the other in some sense, that I think is similar to what you're talking about. All known natural $\mathsf{NP}$-complete problems are p-isomorphic. The idea of the proof is a ping-pong-type argument.</p>

<p>Finally, as another pointer to the literature: Although the notion of $\mathsf{NP}$-complete is not sensitive to the size of the reduction (so long as it's bounded by a polynomial), the Exponential Time Hypothesis (ETH) and its variants <em>are</em> sensitive to super-linear blow-ups in size. So there may be some work on ETH that addresses parts of your question.</p>

CC BY-SA 3.0
2015-09-08T18:30:13.673Z
2015-09-08T18:30:13.673Z
Joshua Grochow
<p>A professor I knew in grad school told me about asking his students to reduce an NP-Complete problem to another, then back to the original, then back again and then watching with amusement as the resulting reductions grew out of control.  Eventually this led me to think that there should be some theory that could get a handle on the size introduced by reductions.</p>

<p>For example, what prevents us from taking a source NP-Complete problem (3-SAT, say) and adding a particular type of structure in the resulting NP-Complete problem (HAMILTONIAN CYCLE, say) such that reducing back to the original (3-SAT) would notice the structure and get back the original instance?  Maybe the original problem would need to be 'pre-structured' so that this type of 'ping-ponging' between NP-Complete problems could occur.</p>

<p>In other words, what prevents us from adding some (polynomial amount of) structure to our NP-Complete problems so that reductions from one NP-Complete problem to another converge in size?  The algorithms for reductions would need to notice the structure embedded in the instance and add their own if need.  I could imagine the features to be indicators for the reduction algorithm so that subsequent reductions would be able to avoid instance inflation.</p>

<p>What do these reductions look like?  What's our current best 'inflation factor'? </p>

<p>Surely I'm not the first to think of this.  Does anyone have references that discuss this type of reduction?  Barring that, does anyone have any ideas on what type of structure needs to be added to achieve this result?  I would be surprised if such a method wasn't possible but I would happily hear about any references about impossibility of such a method.</p>

CC BY-SA 3.0
2015-09-07T14:11:25.433Z
This is connected to whether it is possible to generate in polynomial time instances of an np-complete problem that no polynomial time algorithm can solve.
daniello
CC BY-SA 3.0
2015-09-09T13:38:39.307Z
@daniello: How? I don't quite see the relationship, but sounds interesting...
Joshua Grochow
CC BY-SA 3.0
2015-09-09T15:58:22.717Z
I mean; the Ping-ponging seems irrelevant - one can just consider polynomial time reductions from L to itself. Then the question is; are instances of L generated by polynomial time algorithms that take smaller instances of L harder than general instances of L? The base case of this question are p-time algorithms that generate instances of L from scratch.
daniello
<reductions><np-complete>
NP-Complete Convergent Reductions?
user834
# NP-Complete Convergent Reductions?

(Asked by: username_0 on 2015-09-06)

A professor I knew in grad school told me about asking his students to reduce an NP-Complete problem to another, then back to the original, then back again and then watching with amusement as the resulting reductions grew out of control. Eventually this led me to think that there should be some theory that could get a handle on the size introduced by reductions.

For example, what prevents us from taking a source NP-Complete problem (3-SAT, say) and adding a particular type of structure in the resulting NP-Complete problem (HAMILTONIAN CYCLE, say) such that reducing back to the original (3-SAT) would notice the structure and get back the original instance? Maybe the original problem would need to be 'pre-structured' so that this type of 'ping-ponging' between NP-Complete problems could occur.

In other words, what prevents us from adding some (polynomial amount of) structure to our NP-Complete problems so that reductions from one NP-Complete problem to another converge in size? The algorithms for reductions would need to notice the structure embedded in the instance and add their own if need. I could imagine the features to be indicators for the reduction algorithm so that subsequent reductions would be able to avoid instance inflation.

What do these reductions look like? What's our current best 'inflation factor'?

Surely I'm not the first to think of this. Does anyone have references that discuss this type of reduction? Barring that, does anyone have any ideas on what type of structure needs to be added to achieve this result? I would be surprised if such a method wasn't possible but I would happily hear about any references about impossibility of such a method.

**Tags:** reductions, np-complete

> **Comments:**
> **username_1**: This is connected to whether it is possible to generate in polynomial time instances of an np-complete problem that no polynomial time algorithm can solve.  
> **username_2**: @username_1: How? I don't quite see the relationship, but sounds interesting...  
> **username_1**: I mean; the Ping-ponging seems irrelevant - one can just consider polynomial time reductions from L to itself. Then the question is; are instances of L generated by polynomial time algorithms that take smaller instances of L harder than general instances of L? The base case of this question are p-time algorithms that generate instances of L from scratch.  

---

## 1 answers

### Answer by username_2 on 2015-09-08. Score: 6

*Great* question! I have also had thoughts along similar lines, but not found anything in the literature that fully answers all of these questions. However, for this part of your question, I think a satisfactory answer is given by Berman & Hartmanis:

> what prevents us from adding some (polynomial amount of) structure to our NP-Complete problems so that reductions from one NP-Complete problem to another converge in size?

In some sense, nothing: Berman & Hartmanis showed that if two languages have one-to-one, polynomial-time invertible, length-increasing reductions between them in both directions, then the languages are p-isomorphic. (Here a one-to-one function $f$ is poly-time invertible if there is a poly-time function $g$ such that $g(f(x)) = x$ for all $x$, and $g(y)=\bot$ if $y$ is not in the image of $f$.) Two languages being p-isomorphic basically just means that one is a re-encoding of the other, and thus preserves the "structure" of the other in some sense, that I think is similar to what you're talking about. All known natural $\mathsf{NP}$-complete problems are p-isomorphic. The idea of the proof is a ping-pong-type argument.

Finally, as another pointer to the literature: Although the notion of $\mathsf{NP}$-complete is not sensitive to the size of the reduction (so long as it's bounded by a polynomial), the Exponential Time Hypothesis (ETH) and its variants *are* sensitive to super-linear blow-ups in size. So there may be some work on ETH that addresses parts of your question.


---

