Theory of Computation
-
What is a decision problem?
A decision problem is a question that has two basic outputs: yes or no. An
example of a decision problem would be “is the sky blue?” or “is 1 + 1 equal to
2?”
A decision problem is always associated with a decision procedure, which is a finite set of
steps to solve the problem and generate a decision. (Wikipedia)
- What does it mean for a decision problem to be decidable?
A problem is
decidable if there is a way to construct an algorithm that answers the problem
correctly. (Wikipedia)
- What is the class P? What is the class NP?
The class P consists of problems that are solvable in big-O polynomial
time, aka in time O(n^k) in their worst case. On the other hand, NP-Class consists
of problems that are verifiable in big-O polynomial time, which means it is
easy to check if the answer is correct without the need of additional
information. (Tutorials Point)
- What is the intuitive meaning of the “P versus NP” question?
In general, P includes
easy problems in computation, and NP includes very difficult questions. The
intuition behind the P versus NP statement is that P = NP implies that the hard
problems in in NP should actually have relatively easy solutions. (Tutorial
Point)
-
If you resolve the P versus NP question, how
much richer will you be?
The reward for solving the problem is 1,000,000 granted by Clay Mathematics
Institute. (The Conversation)
Sources: