Restricted Reductions
Agrawal et al. (1997) considered what they called "a radically simple form of gadget reduction", in which each bit describing part of a gadget may depend only on a bounded number of bits of the input, and used these reductions to prove an analogue of the Berman–Hartmanis conjecture stating that all NP-complete sets are polynomial-time isomorphic.
The standard definition of NP-completeness involves polynomial time many-one reductions: a problem in NP is by definition NP-complete if every other problem in NP has a reduction of this type to it, and the standard way of proving that a problem in NP is NP-complete is to find a polynomial time many-one reduction from a known NP-complete problem to it. But (in what Agrawal et al. called "a curious, often observed fact") all sets known to be NP-complete at that time could be proved complete using the stronger notion of AC0 many-one reductions: that is, reductions that can be computed by circuits of polynomial size, constant depth, and unbounded fan-in. Agrawal et al. proved that every set that is NP-complete under AC0 reductions is complete under an even more restricted type of reduction, NC0 many-one reductions, using circuits of polynomial size, constant depth, and bounded fan-in. In an NC0 reduction, each output bit of the reduction can depend only on a constant number of input bits,
The Berman–Hartmanis conjecture is an unsolved problem in computational complexity theory stating that all NP-complete problem classes are polynomial-time isomorphic. That is, if A and B are two NP-complete problem classes, there is a polynomial-time one-to-one reduction from A to B whose inverse is also computable in polynomial time. Agrawal et al. used their equivalence between AC0 reductions and NC0 reductions to show that all sets complete for NP under AC0 reductions are AC0-isomorphic.
Read more about this topic: Gadget (computer Science)
Famous quotes containing the words restricted and/or reductions:
“Love is like some fresh spring, first a stream and then a river, changing its aspect and its nature as it flows to plunge itself in some boundless ocean, where restricted natures only find monotony, but where great souls are engulfed in endless contemplation.”
—Honoré De Balzac (1799–1850)
“The work was like peeling an onion. The outer skin came off with difficulty ... but in no time you’d be down to its innards, tears streaming from your eyes as more and more beautiful reductions became possible.”
—Edward Blishen (b. 1920)