Proving not NP-complete by non-existence of gadget Suppose we suspect a problem to be polynomial time solvable, but we are unable to prove this. So, we attempt to prove that the problem cannot be NP-hard. Known proofs in this direction show that if the problem under consideration is NP-hard, then some widely believed complexity assumption fails (e.g.: Graph Isomorphism).
Is it possible to show that a problem $X$ is not NP-hard by showing the following?
(i) certain type of gadget must exist for a reduction from 3-SAT to $X$, and
(ii) the type of gadget asserted in point (i) cannot exist.
I am afraid such results are not there. Are there at least conjectures that take this direction?
First, I agree w/ Ludwik &amp; other comments that I think (i) is unlikely. Polynomial-time reductions are just polynomial-time algorithms satisfying a certain (fairly flexible! compared to say p-time algorithms computing a fixed function $f$) input-output relationship, and polynomial-time algorithms are just too varied to say that they must take a certain form. You can always compose a gadget-based reduction with a p-automorphism to get something that does not recognizably have gadgets anywhere. (So at the very least you probably want to say &quot;up to p-isomorphism, every reduction must have a gadget of this form&quot;, but &quot;up to p-isomorphism&quot; is a pretty hairy equivalence relation to work with at this level.)
But for (ii), I know of one result like this:

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf, Planarizing Gadgets for Perfect Matching Do Not Exist, MFCS '12.

I don't think I can do much better than quoting the abstract:

To reduce a graph problem to its planar version, a standard technique is to replace crossings in a drawing of the input graph by planarizing gadgets. We show unconditionally that such a reduction is not possible for the perfect matching problem and also extend this to some other problems related to perfect matching. We further show that there is no planarizing gadget for the Hamiltonian cycle problem.