Dr. Christos - Research Questions

1. What is a decision problem?

A decision problem is a question that requires a definite answer of "yes" or "no."

2. What does it mean for a decision problem to be decidable?

A problem is decidable if we can always construct an algorithm that correctly answers the problem.

3. What is the class P? What is the class NP?

P is the class of problems that can be solved in polynomial time. NP is the class of problems whose solutions can be verified in polynomial time.

4. What is the intuitive meaning of the "P versus NP" question?

The P versus NP question asks whether every problem we can quickly check can also be solved quickly. It focuses on whether problems where solutions can be verified efficiently can also have their solutions found efficiently.

5. If you resolve the P versus NP question, how much richer will you be?

If you resolve the P versus NP question, you will be $1 million richer. P versus NP is one of the Clay Mathematics Institute Millennium Prize Problems, which offers a million-dollar prize for solving it.

Sources

GeeksforGeeks - Decidable and Undecidable Problems

Britannica - Decision Problem

GeeksforGeeks - P vs NP Problems

Business Insider - P vs NP Millennium Prize

Home Page

```