Prof. Christos/ Theory

1.What is a decision problem?
In computational theory, a decision problem is defined as a problem with a yes/no,true/false answer.

2. What does it mean for a decision problem to be decidable?
A decision problem is considered to be decidable if it can be solved under a finite number of steps to stop all input and reach a valid conclusion.,%2C%20algorithmically%20solvable%2C%20recursively%20solvable.

3. What is the class P? What is the class NP?
In a P class, problems are solvable under polynomial time. While in an NP class, the problems can be verified whether they're true or false under polynomial time.,are%20called%20intractable%20or%20superpolynomial.

4. What is the intuitive meaning of the “P versus NP” question?
A P versus NP question pretty much asks that if a problem is verifiable, is it also solvable under a polynomial time.

5. If you resolve the P versus NP question, how much richer will you be?
A million dollars richer, but later on I'll probably rival Jeff Bezos in terms of wealth.

Haolin Wang

Sarissa theme designed by iozcelik

Haolin Wang