1. What is a Decision Problem?
A decision problem is a computational problem that can be posed as a yes/no question on a set of input values. For example, determining whether a given number is prime is a decision problem. Source: Wikipedia
2. What Does It Mean for a Decision Problem to Be Decidable?
A decision problem is decidable if there exists an algorithm (or Turing machine) that can determine the answer (yes or no) for every possible input in a finite amount of time. An undecidable problem has no such algorithm. Source: GeeksForGeeks
3. What Is the Class P? What Is the Class NP?
- P (Polynomial Time): Decision problems solvable by a deterministic Turing machine in polynomial time. Source: GeeksForGeeks
- NP (Nondeterministic Polynomial Time): Decision problems where a solution can be verified in polynomial time. Source: Wikepedia
4. What Is the Intuitive Meaning of the “P vs NP” Question?
The P vs NP question asks whether every problem whose solution can be verified quickly (in polynomial time) can also be solved quickly (in polynomial time). In other words, is P equal to NP? This is a fundamental unsolved question in computer science with significant implications for fields like cryptography, optimization, and algorithm design. Source: MIT News
5. If You Resolve the P vs NP Question, How Much Richer Will You Be?
Solving the P vs NP question would be a monumental achievement in theoretical computer science. If you solve the P vs NP problem, the immediate financial reward is $1 million USD, awarded by the Clay Mathematics Institute as part of the Millennium Prize Problems. Source: Clay Mathematics Institute