Research Notes for Dr. Chritos

What is a decision problem?

A decision problem is a computational question that yields a binary output: either "yes" or "no" for a given set of input values. Formally, it can be defined as determining whether a given input string belongs to a specific formal language. Two standard examples of decision problems include:

• Primality Testing: Determining whether a given integer $n$ is a prime number.
• Graph Connectivity: Determining whether two specific vertices in a graph are connected by a path.

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

A decision problem is decidable (or computable) if an algorithm exists that can process any valid input and yield the correct "yes" or "no" answer in a finite number of steps. If no algorithm can guarantee termination with a correct answer for every input, the problem is classified as undecidable. The Halting Problem formulated by Alan Turing is a classic example of an undecidable problem.

What is the class P? What is the class NP?

Class P (Polynomial Time): The class of decision problems that can be solved by a deterministic Turing machine within a time bound proportional to a polynomial function of the input size, expressed as $O(n^k)$ for some constant $k$. Problems in P are considered computationally tractable.

Class NP (Nondeterministic Polynomial Time): The class of decision problems for which a candidate solution can be verified by a deterministic Turing machine in polynomial time. Alternatively, these are problems that can be solved in polynomial time using a nondeterministic Turing machine.

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

The intuitive meaning of the "P versus NP" question centers on whether every problem whose solution can be easily verified by a computer can also be easily solved by a computer from scratch.

• If $P = NP$, finding a solution to a complex problem is inherently as easy as checking a proposed solution.
• If $P \neq NP$, verifying the correctness of a solution is fundamentally easier than discovering that solution independently.

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

Resolving the P versus NP question yields a cash award of $1,000,000 USD (approximately 125,000,000 ETB). This monetary prize was established by the Clay Mathematics Institute in May 2000 as one of the seven Millennium Prize Problems.

Reference Links

• Clay Mathematics Institute: The P vs NP Problem
• Wikipedia: Decision Problem
• Wikipedia: P versus NP problem
• NIST Dictionary of Algorithms and Data Structures: Decidable Problem