Theory of Computation Research
August 6, 2022
What is a decision problem?
A decision problem is a type of problem in Theoretical Computer Science where the answer
can only be yes or no. For example, a problem defined as “Find the best possible solution”
is not a decision problem while a problem defined as “Is there a solution of size k?”
where k is an input is a decision problem.
What does it mean for a decision problem to be decidable?
A decision problem is decidable if the set of natural numbers (1, 2, 3, …), which is
taken as the set of inputs for which the answer to the decision problem is yes, can be
solved by an algorithm. This algorithm needs to receive the number input, process it
for a finite amount of time, and then output whether the number belongs in that set of
natural numbers that lead to a yes answer or not.
What is the class P? What is the class NP?
There are programs that solve specific problems and the time it takes for the program
to solve them is either fast or slow. And then there are problems in the middle;
problems to which we don’t know whether there exists a fast program that solves it or
not. In Theory of Computation, the class P groups problems to which a fast program that
solves it is known such as multiplication and sorting and the class NP includes problems
to which correct solutions can be verified in a reasonable amount of time such as the
Travelling Salesman Problem and Circuit Satisfiability Problem.
What is the intuitive meaning of the “P versus NP” question?
Quoted directly from the video, “Does being able to quickly recognize correct answers
mean there’s also a quick way to find them?” The primality problem which is “Given
natural number n, is n prime?” used to be an NP problem before it was found out to be
a P problem. The P versus NP question then asks whether every NP problem is a P problem
or there are some NP problems that really are harder to solve than P problems. The
consensus is that P does not equal NP which is the most likely answer because, in a more
philosophical point of view, that is the way the universe seems to work. To quote Scott
Aaronson, an American theoretical computer scientist, if P=NP, “Everyone who could
appreciate a symphony would be Mozart”. If both easy problems and hard problems had easy
solutions, then if you could solve easy problems, you could solve any hard problem.
Knowing that would greatly change the way we view the universe.
If you resolve the P versus NP question, how much richer will you be?
Exactly one million dollars richer.
Links to sources used:
YouTube Video: Decision Problems - Intro to Theoretical Computer Science
Wikipedia Article on Decision Problems, Decidability Section
Wikipedia Article on Computable Sets
Youtube Video: P vs. NP and the Computational Complexity Zoo
Quora Question on NP Problems That Were Later Proved to Also be in P
Further Reading:
2009 'MIT News' Article On P versus NP
2019 'Towards Data Science' Article on P versus NP
'New World Encyclopedia' on Decision Problems