Finding Momentum

Dis­claimer: about 95% of you won’t get this. The other 5% should con­sider get­ting a life.

So we’re in CS lec­ture (this is with Prof. Papad­mitrou), and one stu­dent in the front raises his hand and asks, “Isn’t the Trav­el­ing Sales­man Prob­lem not yet proven NP-complete?”

Papad­mitrou turns around with a con­cerned expres­sion on his face. “No, it is def­i­nitely NP-complete. What makes you think that?”

“Oh, I dunno. I just thought I heard you say it or read it somewhere.”

“It is most def­i­nitely NP-complete.” Papad­mitrou talks for a few moments about why it is so. “I should know, I proved it in my the­sis.” Then he fol­lows it up with this smile.

Our jaws all drop. Everybody’s think­ing the same thing: this man is a gang­ster. There is laugh­ter and applause for a minute or two.