Presentation3 Questions

1. What is a decision problem?

A decision problem is any problem that the answer to it is either yes or no.

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

According to xlinux.nist.gov website, a decision problem to be decidable may be completed in a finite number of steps by an algorithm that halts on all inputs.

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

P P is problems to be solved in polynomial time. NP is a problems to be solved by a Non-deterministic turing Machine in Polynomial time, and it is called "Non-deterministic Polynomial Time". Source

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

According to MIT News, it means that if any solution to any problem, can be viewed in polynomial time, then it can be viewed in that time.

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

Their are seven questions, that if anyone answer it, they get a million dollar Source