NP-Complete Convergent Reductions?

Question

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.

Answer 1

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.