2
$\begingroup$

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?)

$\endgroup$
  • $\begingroup$ I think it's probably mostly gadget reductions that are "natural". $\endgroup$ – Raphael Nov 9 '17 at 6:49
  • $\begingroup$ 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. $\endgroup$ – Pawan Kumar Nov 9 '17 at 7:06
  • 1
    $\begingroup$ 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! $\endgroup$ – Raphael Nov 9 '17 at 8:18
4
$\begingroup$

Natural reductions are a special case of Karp reductions, with an extra condition stating that the output's length depends only on the input's length (and not structure). This concept can be applied to many forms of many to one reductions, so I guess you could talk about natural logspace reductions.

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.

Finding an example of a "natural" non-natural reduction (even if a natural one is known) is harder, but I guess that if you go over enough reductions you will find one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.