Questions:
1. The P v. NP problem asks whether all problems whose solutions can be verified in some time can also be solved in a comparable length of time. What is this length of time called for the purpose of this problem?
2. There is another length of time called ___________ ____. Whereas the answer to Q1 denotes a length that depends on the size S of the input problem raised to some power (e.g. S2), the answer to Q2 is a length proportional to an integer raised to the input size (e.g. 2S). As S increases, 2S will increase faster than S2. Fill in the blank.
3. Name the Colorado-based private foundation that offers a million dollars as cash prize each to the solutions of seven unsolved problems – one of which is the P v. NP problem.
4. The solution to the P v. NP problem has significant consequences for cryptography. For example, the ___ algorithm to encrypt information takes advantage of the fact that it is very difficult to identify the prime number factors of a very large number within a certain amount of time. Fill in the blank.
5. X, an American mathematician, wrote in 1955 to the U.S. National Security Agency that he believed solving a sufficiently complicated problem would consume a lot more time than verifying the solution. X became popular for his work in game theory. Name him.
Answers:
1. Polynomial time
2. Exponential time
3. Clay Mathematics Institute
4. RSA algorithm
5. John Nash
