I recently expanded the Wikipedia article on gadgets, the basic building blocks of most NP-completeness proofs, after its previous poor state led another editor to try to get it deleted.

While doing so, I discovered that we didn't already have an article on the Berman–Hartmanis conjecture according to which every two NP-complete problems should be related by a polynomial-time isomorphism, so I wrote one. Supposedly nobody believes this any more but despite that there are recent papers such as Agrawal and Watanabe CCC 2009 that seem to be more positive than negative.

I'm not a complexity theorist, so it's entirely likely that I've misunderstood some of the sources. If so, please correct me.




Comments:

ext_933347:
2012-02-29T12:06:06Z

Very nice! Gadgets are one of the main tools in the TCS toolbox, and thus a major conceptual contribution. Good to see them described per se.