Computational Theory Research

1. What is a decision problem?

is a problem that’s has only yes or no on any input values. For example, a question such as “Is X palindrome?” has only a yes or no answer.

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

It means that it can be solved by an algorithm in a finite number of steps

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

The p stands for Polynomial Time and it is a collection of decision problems that can be solved by a deterministic machine in polynomial time. Their solutions are easy to find. Whereas NP stands for Non-deterministic Polynomial Time, and it is a collection of decision problems that can by solved by a non-deterministic machine in polynomial time, their solutions are harder to find.

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

It asks whether a problem whose solution can be checked quickly can be solved quickly.

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

The P versus NP question is one of the seven Millennium Prize Problems, meaning that if your resolve the statement a million dollars will get incremented into your bank account.

Sources:

https://en.wikipedia.org/wiki/Decision_problem#:~:text=In%20computability%20theory%20and%20computational,given%20natural%20number%20is%20prime.
https://www.geeksforgeeks.org/types-of-complexity-classes-p-np-conp-np-hard-and-np-complete/
https://www.studysmarter.co.uk/explanations/computer-science/theory-of-computation/p-vs-np/#:~:text='P'%20stands%20for%20'Polynomial,can%20also%20be%20solved%20quickly.
https://gizmodo.com/if-you-solve-this-math-problem-you-could-steal-all-the-1836047131