Algorithm can be described as a sequence of instructions to solve a
problem. These problems may range from mathematical to decision
problems. But are these algorithms always solvable in polynomial time
(n^k for any input n) or even verifiable in polynomial time?
The answer is no. To have a deeper insight, let's look into the categorized classes of the problems.
P (Polynomial): The class of all decision problems for which there exists an algorithm that can be solve the problem in polynomial time (n^k for input n and any constant k).
Example: Binary search, merge sort, etc.
NP (Non-deterministic Polynomial): The class of all the problems whose answer if "yes" can be verified in polynomial time.
Example: All problems that are in P, Hamiltonian cycle.
P ⊆ NP
NP-Complete: A problem is NP-Complete if it is in NP and is as hard as any other problem in NP. In simple words, set of all problems 'x' such that any other problem 'y' in NP can be reduced to 'x'.
Example: Traveling salesman problem.
y ≤ₚ x denotes:
NP-Hard: It is even harder than NP-Complete. A problem 'x' is NP-Hard if there exists an NP-Complete problem 'y' such that 'y' is reducible to x.
Example: Vertex Cover
Problem Verifiable Solvable Difficulty
(In Polynomial Time)
P Yes Yes ⬇
NP Yes Yes/No ⬇
NP-Complete Yes Unknown ⬇
NP-Hard Yes/No Unknown ⬇
The answer is no. To have a deeper insight, let's look into the categorized classes of the problems.
P (Polynomial): The class of all decision problems for which there exists an algorithm that can be solve the problem in polynomial time (n^k for input n and any constant k).
Example: Binary search, merge sort, etc.
NP (Non-deterministic Polynomial): The class of all the problems whose answer if "yes" can be verified in polynomial time.
Example: All problems that are in P, Hamiltonian cycle.
P ⊆ NP
NP-Complete: A problem is NP-Complete if it is in NP and is as hard as any other problem in NP. In simple words, set of all problems 'x' such that any other problem 'y' in NP can be reduced to 'x'.
Example: Traveling salesman problem.
y ≤ₚ x denotes:
- x is at-least as hard as y.
- y is polynomial time reducible to x.
- If x can be solved in polynomial time y can also be.
- If y cannot be solved i polynomial time x cannot be.
NP-Hard: It is even harder than NP-Complete. A problem 'x' is NP-Hard if there exists an NP-Complete problem 'y' such that 'y' is reducible to x.
Example: Vertex Cover
Problem Verifiable Solvable Difficulty
(In Polynomial Time)
P Yes Yes ⬇
NP Yes Yes/No ⬇
NP-Complete Yes Unknown ⬇
NP-Hard Yes/No Unknown ⬇