What are the theoretical limitations of computer power? Modern computers can solve complex problems with astonishing speed. Yet, certain ordinary tasks appear to be too hard even for computers. For example, computers can multiply numbers that have thousands of digits, in a fraction of a second. But the reverse problem, that of finding the factors of a thousand digit number, seem to require millennia. All known methods for factoring numbers involve searching for the factors across many possibilities, and the magnitude of that search may be astronomical. Perhaps a fast way of factoring numbers may be found some day. Does such a method even exist? No one knows.

The great logician Kurt Gödel was among the first to raise this type of question in a remarkable 1956 letter to John von Neumann, the famous mathematician and computer pioneer. Gödel asked von Neumann whether certain computational problems, which seem to involve searching through many possibilities, could be solved instead without resorting to brute force search. Today the precise form of this question is known as the P versus NP question, one of the most important unanswered questions of contemporary mathematics and theoretical computer science.

In this talk, we will review the P versus NP question, its history including Gödel's letter, some practical implications for cryptography and other fields, and prospects for the future. No mathematical background will be assumed.