The First question

Christos Research:

• What is a decision problem? According to Wikipedia a decision problem is a “ yes or no question on an infinite set of inputs”. Meaning we find out if a specific statement is true or false on an infinite set of inputs. • What does it mean for a decision problem to be decidable? A decision problem is decidable when we can develop an algorithm that will help us solve the problem correctly. • What is the class P? What is the class NP? Class P includes all problems that can be solved in ‘polynomial’ time. Their solutions are easy to find and often tractable. Class NP includes all problems that can be solved by ‘non-deterministic machine in polynomial time’. Their solutions are hard to find. (referenceTypes of Complexity Classes | P, NP, CoNP, NP hard and NP complete - GeeksforGeeks) • What is the intuitive meaning of the “P versus NP” question? A simple meaning to the ‘P vs NP” question is whether questions that are quickly verified if they can also be quickly solved. Since P are questions that are easily solved and NP involves difficult questions, it would mean that hard problems do actually have an easy way to be figured out. • If you resolve the P versus NP question, how much richer will you be? Once you have the answer, you will be a million dollar more richer because of how important it is to be solved in the world of computing. You could be even more richer depending on your scruples.

Malak Ibrahim

Sarissa theme designed by mmibrahi

Malak Ibrahim

Computer Science, Robotics