Theory of Computing

Talhah Peerbhai published on
2 min, 361 words

What is the theory of computing?

The theory of computing is a branch of computer science which studies how problems can be solved using algorithms and how efficiently they can be solved.

What is a decision problem?

It is a problem which can be modeled as a yes-no question that is tested on an infinite set of inputs.

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

Problems can either be decideable or undecideable. A problem that is decideable is one which we can always construct an algorithm that can answer the problem correctly. For each input there is a yes or no answer.

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

The class P consists of all problems that are solvable in polynomial time. The class NP is the set of decision problems that can be solved in a non-determistic machine in polynomial time. It therefore contains problems that cannot be solved effectively. All solutions for problems in this class can be checked effectively.

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

This question asks whether class P and NP are identical. Whether each NP problem is also a P problem. If P happens to be equal to Np every NP problem would then have a shortcut as P is easily solvable.

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

The P versus NP problem is a millenium prize problem, meaning you'll walk off with $1 million. You'll also walk of with fame among computer scientists and mathematician.

Sources:

Theory of Computation Wikipedia
Decision Problem igi-global
Decidable Problem geeksforgeeks
Class P and NP
What is P vs NP? technologyreview Millenium prize problem businessinsider