Prof. Christos / Theory

What is a decision problem?

A decision problem is a category of questions in mathematics and formal logic that requires an algorithm or repetitive procedure to determine a definitive answer of "yes" or "no" after selecting a specific question from the class. An example of this type of problem is determining whether two natural numbers x and y can be evenly divided. The answer to this question is dependent on the values of x and y and can only be "yes" or "no".

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

A decidable language is one that can be solved by an algorithm that halts in a finite number of steps. It is also known as a totally decidable problem or algorithmically solvable.

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

P is the set of problems that can be solved by a deterministic Turing machine in polynomial time, while NP is the set of problems that can be solved by a non-deterministic Turing machine in polynomial time.

What is the intuitive meaning of the “P versus NP” question?

"Does P equal NP?" is a question about whether problems that can be verified in polynomial time can also be solved in polynomial time. Finding a polynomial-time solution to an NP-complete problem can lead to solutions for all others. These problems are common in real-life scenarios, such as scheduling tasks and the traveling-salesman problem.

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

You may have heard of the famous P vs NP problem. If you can prove or disprove its cryptic equation, you could win millions, even billions, depending on your ethics.