Answers to Professors Christos’s presentation

Q1. What is a decision problem? A1. A decision problem is one where you would usually have to ask yourself, is there a specific solution for this problem? The solution would usually contain certain characteristics. In more broad terms its more like a yes/no question. Q2. What does it mean for a decision problem to be decidable? A2. For the decision problem we had to answer the input in either yes or no, If we can find an algorithm to solve the problem then we say its decidable. For example; in carols case, he wanted to find an algorithm to see whether the app will crash or not. This scenario is undecidable because theres no such existing algorithm. Q3. What is the class P? What is the class NP? A3. P is a sub-class of NP, it stands for polynomial time. Its basically problems that we have algorithms or solutions for and can solve them in polynomial time, just like the case of Alex who wanted a route to visit every stop exactly once.There was an algorithm so its considered P class. Over time a different subset was found that P was also a subset of. NP. It stands for non-deterministic polynomial time. It means that NP problems don't have an algorithm that can solve them in polynomial time. Q4. What is the intuitive meaning of the “P versus NP” question? A4. The P versus NP question has been an ongoing question. Most people believe that P cannot equal NP, as that will change a lot of things. This statement basically means that if P=NP then a polynomial time algorithm for hard NP problem has been discovered. This will mean that we can solve hard questions in a quicker more efficient way. Q5. If you resolve the P versus NP question, how much richer will you be? A5. If you ever get lucky enough, you’ve secured 1000000$ in the bag.