![[info]](http://l-stat.livejournal.com/img/userinfo.gif?v=92.1){kind=small}
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.
February 29 2012, 12:06:06 UTC 2 months ago