Theory & Algorithms

Any computational problem which can be formulated as a yes/no question is a decision problem.

For a decision problem to be decidable means to have an algorithm which solves it.

• The class P refers to all the problems which are solvable "efficiently" in polynomial time. (easy~problems)
• The class NP refers to all the problems which are solvable "non-efficiently" in nondeterministic polynomial time and deterministic exponential time. (hard~problems)

Intuitive meaning of the P vs NP question:

• if P = NP then there exists efficient algorithms to solve nondeterministic polynomial time problems, which will help us solve many real life problems.
• if P != NP then it means that finding a solution to NP problems are fundamentally difficult than to P problems.

Well, if you resolve P vs NP, you become a millionaire. (if you are not already)