New answers tagged reductions
6
First, I agree w/ Ludwik & 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 ...
5
I would imagine it very difficult to prove that "[a] certain type of gadget must exist for a reduction from 3-SAT to X". You could state that one type of gadget would enable a specific reduction, or even a family of reductions, but there might still be a different reduction possible that you haven't thought of.
If you could indeed prove that every ...
Top 50 recent answers are included
