Tag Archives: P vs NP

P vs NP: What’s the problem?

Posted on September 1, 2010 by Brent

As promised (better late than never), I’m going to begin explaining the (in)famous P vs NP question (see the previous post for a bit more context). As a start, here’s a super-concise, 30,000-foot version of the question: Are there problems … Continue reading →

Posted in computation, open problems | Tagged , , , , | 9 Comments

P ≠ NP?

Posted on August 10, 2010 by Brent

A few days ago, Vinay Deolalikar, a Principal Research Scientist at HP Labs, began circulating a draft of a paper entitled “P ≠ NP”. The mathematics and computer science communities immediately erupted in a frenzy of excitement and activity. The … Continue reading →

Posted in computation, links, open problems, people, proof | Tagged , , , | 7 Comments