Theory of Computing
What is a decision problem?
A decision problem is a problem that only gives an answer in terms of “yes” or “no”. For example, is one an even number?
What does it mean for a decision problem to be decidable?
A decision problem is decidable if there exists an algorithm that can solve the problem and return the correct answer.
What is the class P? What is the class NP?
P-class problem are problems that can be solved in polynomial time. P in P-class stands for Polynomial Time. Similarly, NP-class problems are problems that can be verified in polynomial time. NP in NP-class stands for Non-deterministic Polynomial Time.
What is the intuitive meaning of the “P versus NP” question?
P are a set of problem that are relatively easy, whereas NP are a set of problems that are extremely difficult. P vs NP means that the difficult problems of NP have easy solutions, like P.
If you resolve the P versus NP question, how much richer will you be?
US$1,000,000 richer.
Summary on Professor Kristos' talk about the theory of computation
What does the Professor teach?
Professor Kristos teaches four courses which are all theoritical computer science courses. Two of the courses, Great Theoritical Ideas and Algorithm Design are required courses whereas the other two are electives.
What did he talk about in the lecture?
Professor Kristos basically talked about three different types of problems in computer science: problems that can be solved efficiently, problems that can be solved but their solution are not efficient, and problems that cannot be solved.
What I felt from the lecture?
Even before I joined CMU, Great Theoritical Ideas in Computer Science was one of the courses that I was most interested in. The professor explained the concept very well, and you can see that he's obviously very enthusiastic about the topic. I'm very much looking forward to GTI and am most definitely taking his other electives.