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.