Theory of Computation

What is a Decision Problem?

A decision problem is a problem that can be phrased as a yes/no question. Specifically, it involves determining whether a given input satisfies a particular property or condition.

What Does it Mean for a Decision Problem to be Decidable?

A decision problem is when there exists an algorithm that will provide a correct yes/no answer for every possible input in a finite amount of time. In other words, there’s a systematic method to solve the problem.

What is the Class P?

The class P consists of decision problems that can be solved in polynomial time. This means there exists an algorithm that can determine the answer to the problem in a time that grows polynomially with the size of the input.

What is the Class NP?

The class NP consists of decision problems for which a given solution can be verified in polynomial time. All problems in P are also in NP, but it’s not known whether all NP problems can be solved in polynomial time.

What is the Intuitive Meaning of the “P versus NP” Question?

The P versus NP question asks whether every problem for which a solution can be quickly verified (NP) can also be quickly solved (P). In other words, it questions whether P = NP or P ≠ NP. If P = NP, it means that for every problem where we can check a solution efficiently, there is also a way to find that solution efficiently.

If You Resolve the P versus NP Question, How Much Richer Will You Be?

Resolving the P versus NP question could lead to a 1 million dollar prize and other awards by various institutions.