What was your ‘proof’? As a computer science person I think about this question all the time.
Benji Lampel

It wasn’t even really a proof. I was writing a bin packing algorithm in undergrad (as one does) and had come up with some insight that I thought allowed me to solve it in polynomial time. I only vaguely remember the idea of the algorithm (this was late 90s) but it involved claiming I could resize the boxes into an equivalent set that I could pack in polynomial time. Now, any sane person would double and triple and nuple-check their algorithm/idea at this point. What I did was begin looking through the list of NP-HARD problems to see how to convert bin packing into each one —

— I seriously think my mind-set was all, “And Traveling Salesmen? You’re welcome. Map colorists? You’re welcome. And government intelligence agencies? You’re — oh, you guys don’t seem very appreci — what do you mean I’ve just just unraveled decades of stabilization efforts and plunged the globe into chaos?

But so there I am reading how to convert bin packing into traveling salesman and I’m all what is this step here about? Why do they have this entire extra idea here that it is totally unneces — oh. Huh.

And that’s when I realized that this box size transformation thing I was doing did not create an equivalent class. Ish. It was a little more complicated than that but that was the gist. On the down side, I did not win a million dollars and catapult myself into instant academic stardom. On the upside, I also did not plunge the intelligence agencies of the world into an unbridled panic that would have surely annihilated us all. So… you’re welcome, people of planet Earth. You’re welcome.

Show your support

Clapping shows how much you appreciated m. scott veach’s story.