For decades, it's been the most compelling--and the most seemingly unsolvable--problem in computer science. Does P = NP? In other words, can a problem that can be checked by a computer also be solved by a computer? HP Labs mathematician Vinay Deolalikar claims to have definitively answered the question.
But CSAIL's Scott Aaronson is certain that Deolalikar can't back it up. So certain, in fact, that he's staking $200,000--plus his house--on it. "This is not a problem that’s going to be solved by just combining or pushing around the ideas that we already have," Aaronson said in an interview with MIT News.
Deolalikar claims to have proven once and for all that P does not equal NP. But Aaronson believes that Deolalikar's argument is deeply flawed, and that the problem can't be solved without major advances in human understanding. Read the rest of Aaronson's remarks here.