hw5. Prof Christos. Theory

Decision Problem

Decision problems are a set of problems/questions can be answered by "yes" or "no", with help of some algorithms or procedures.
If the set of inputs with answer="yes" is a recursive set, then the decision problem is called decidable or effectively solvable.

P vs NP

"P versus NP" is one of the 7 Millennium Prize Problems. Here, P denotes the set of problems which can be solved in polynomial time.
NP denotes the set of problems, where provided answer can be checked for correctness in polynomial time. The "P versus NP" problem asks
to prove whether P=NP, and the winner receives $1,000,000 for correct solution.

Let's take an example. In the sudoku game, we can check if the given solution fulfills all the conditions in polynomial time. So,
sudoku is a part of NP problems. But, there are no known ways of solving the sudoku in polynomial time. Thus we don't know if sudoku
is a part of class P problems.

References

1. https://en.wikipedia.org/wiki/Decision_problem
2. https://www.britannica.com/topic/decision-problem
3. https://en.wikipedia.org/wiki/P_versus_NP_problem