Theory

What is a decision problem?

Answer:

A decision problem is a question with exactly two possible answers: Yes or No.

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

Answer:

A decision problem is decidable if there exists an algorithm that always produces the correct Yes/No answer in a finite amount of time.

What is the class P?

Answer:

The class P contains decision problems that can be solved in polynomial time by a deterministic algorithm. These are considered efficiently solvable or tractable problems.

What is the class NP?

Answer:

The class NP contains decision problems for which a proposed solution can be verified in polynomial time by a deterministic algorithm. Finding the solution might be hard, but checking it is efficient.

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

Answer:

Informally: If verifying a solution is easy, is finding one also easy?

P: problems where solutions can be found quickly.
NP: problems where solutions can be checked quickly.
Example: solving a puzzle or writing a code may take hours, but checking a finished puzzle or tracing the code takes much less than that.
Most computer scientists believe P ≠ NP, but it remains unproven.

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

Answer:

At minimum, a correct proof of P vs NP wins the Clay Mathematics Institute's Millennium Prize of $1,000,000 and worldwide recognition. If you prove P = NP constructively with a practical algorithm, the practical value could reach billions by transforming cryptography, optimization, drug discovery, logistics, and more.