P vs NP — Dr. Christos

1. What is a decision problem?

A decision problem is a computational or mathematical problem that outputs either yes or no answers depending on the inputs.

2. What does it mean for a decision problem to be decidable?

A decision problem is decidable/solvable/computable if and only if there is an algorithm that, when applied to an instance of the problem, evaluates to either true or false correctly according to whether or not the answer to the instance is "yes" or "no". This must be done within a finite time frame.

3. What is the class P? What is the class NP?

P is the set of all decision problems that can be solved by a deterministic algorithm in polynomial time.

NP is the set of all problems that can be solved by a nondeterministic algorithm or verified in polynomial time. Non-deterministic algorithms are algorithms where when solving decision problem p:

• For each input to d for which the answer should be yes, there is a guess that, when it is checked in the checking stage, will result in the answer yes
• For each input to d for which the answer should be no, there is no guess that it can make in the guessing stage that when it is checked will result in the answer yes
• Basically, guessing instead of solving, and then checking guesses

4. What is the intuitive meaning of the "P versus NP" question?

The intuitive meaning is to find the relationship between P and NP i.e. if a solution to a problem can be checked efficiently, can that problem be solved efficiently? If this is true then it means many of the unsolved problems could be solved and if not, then it determines whether further research is feasible.

5. If you resolve the P versus NP question, how much richer will you be?

The Clay Mathematics Institute offers a $1,000,000 prize for a correct solution to any of its seven Millennium Prize Problems, where one of them is the P vs NP. So, you would be a million dollars richer and much more famous.

Sources used:

• web.stanford.edu — CS103: P vs NP
• cs.hunter.cuny.edu — CSCI 335 lecture notes, Chapter 10
• cs.cmu.edu — 15-212 handout: Computability

← Previous: Week 2 — Programming Languages  ·  Next: Week 4 — Human-Computer Interaction →