# "Natural" reductions vs "Polynomial-time many-one" reductions (Karp Reductions)

For two problems $A$ and $B$ and a Karp Reduction $R$ from $A$ to $B$, we call the reduction $R$ natural if, for any instance $I$ of problem $A$, the size of $R(I)$ (as well as the possible numerical parameters of $R(I)$ depends only on the size of $I$ and the sizes of $I$ and $R(I)$ are polynomially related.

We know that all the text-book reductions (from SAT to 3-SAT, 3-SAT to Vertex Cover, Hamiltonian Cycle etc.) are natural in the above sense. In fact, all the natural known "NP-complete" problems are complete under "Natural" reductions.

I have following two questions:

1. Is it possible for a Karp-reduction to be "non-natural" in the above sense?
2. Are "natural" reductions only a special case of "Karp" reductions or Can we generalize them for other reductions (like logspace or linear time reductions)?

To understand the context better: Kabanets-Cai[1999] in his seminal paper proved that Minimum Circuit Size Problem (popularly known as MCSP) being NP-hard under so-called "natural" reductions leads to class $E$ having superpolynomial circuit size. Then, recently Murray-Williams[2015] proved that MCSP being NP-hard under "Polynomial-Time" reductions leads to $EXP \neq NP \cap P/poly$ (This is weaker than Kabanets-Cai result). So, surely "natural" reductions are more strict than "polynomial-time" reductions. (or Am I missing something here?)

• I think it's probably mostly gadget reductions that are "natural".
– Raphael
Nov 9, 2017 at 6:49
• Yes. But as Ariel pointed out in the answer that Gadget reductions can be made "non-natural" too by slight tweaking. I suspect there is no natural NP-complete problem known which fails the "natural" reduction test. Not sure though. Nov 9, 2017 at 7:06
• IIRC there are plenty of NP-complete problems for which the "well-known" reductions are not gadget reductions. I suspect that other types are more often non-natural, but I'd have to read to find out. That's your job, though: pick up Garey/Johnson and have a look!
– Raphael
Nov 9, 2017 at 8:18

Obviously a karp reduction can be non-natural (otherwise the definition would be of no use). Think about a reduction from clique to SAT, I can make it non natural by first checking whether the graph is planar, and in case the answer is yes output some fixed non satisfiable formula (suppose the parameter $k$ is greater than $4$). This breaks naturality, since now the output formula's length depends on the planarity of the input graph.