← back to main site
Research Update

Week 2 — Decision Problems and P vs NP

Topic presented by Prof. Christos Kapoutsis · Baraa Nsour
Q1

What is a decision problem?

A decision problem is one, in which, after performing a set of steps on it, will yield an answer given by a "yes" or "no". In essence, it is one in which a theorem of the problem can be either proved or disproved.

Q2

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

A decidable problem is one where we can construct an algorithm for it that will always give a solution to the problem. There is a different term called a Turing Decidable problem, which is one for which a Turing machine will provide a yes/no answer to every input.

Q3

What is the class P? What is the class NP?

The class P is a collection of problems which a computer would be able to solve efficiently. Hence, a solution would be efficient. In contrast, class NP is the collection of problems for which no efficient solutions exist. Furthermore, NP problems have solutions which can easily be verified as True/False, but cannot (theoretically) be computed as quickly.

Q4

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

The P versus NP in essence is the question of whether a question whose solution is quickly verifiable can always have an efficient solution given by a computer. Many scientists believe that that is not the case.

Q5

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

1 million dollars richer (which isn't much in today's economy, honestly. Kind of disappointing. More money would be a greater incentive.)

Further reading

Decision problem Britannica — background on decision problems and the Entscheidungsproblem. (Q1) Decidable and Undecidable Problems in Theory of Computation GeeksforGeeks — what decidability means, with examples on either side of the line. (Q2) Types of Complexity Classes: P, NP, CoNP, NP-Hard and NP-Complete GeeksforGeeks — how the major complexity classes are defined and how they relate. (Q3) P vs NP Problems GeeksforGeeks — the open question stated plainly, and why it matters. (Q4)