Prof. Christos / Theory

Questions & Answers

1. What is a decision problem?
This refers to a yes or no question

2. What does it mean for a decision problem to be decidable?
The term "decidable" refers to an algorithm that consistently yields the right answer in a finite amount of time.

3. What is the class P? What is the class NP?
Class P is when the problems can be solved by a computer in a short amount of time. That noted, Class NP problems are those for which a "yes" response may be confirmed quickly

4. What is the intuitive meaning of the “P versus NP” question?
If verification is simple, is solution also simple? is the question posed by the P vs. NP debate; notably, with the proof of P = NP, we could observe huge transformations in domains such as optimization and cryptography.

5. If you resolve the P versus NP question, how much richer will you be?
The Millennium Prize for solving it is $1 million; however, I would not like to categorize my "richness" in terms of monetary value, but in terms of the impact I would have.

References

  1. Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2012.
  2. Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
  3. Lance Fortnow, “The Status of the P versus NP Problem,” Communications of the ACM, 52(9):78–86, 2009. https://cacm.acm.org/research/the-status-of-the-p-versus-np-problem/