Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top