We have come across many types of algorithm for solving a problem like sorting array element, Searching in linked list , traversing in tree and many more In addition to this there are some another algorithm which we generally don’t use and don’t much interested to know like halting problem in Turing Matching, Finding whether a given grammar is ambiguous or not and many more.So we have categorized algorithm in different group based on there running time.Like categorized Fruit based on Vitamin which contains in side.In the same way we have categorized Algorithm based on there running time or solvable nature of problem.
Category 1: Polynomial Running time Algorithm (P Class)
All of the algorithms we have studied thus far have been polynomial-time algorithms: on inputs of size n, their worst-case running time is O(n^k) for some constant k. It is natural to wonder whether all problems can be solved in polynomial time. The answer is no. For example, there are problems, such as Halting Problem, 3-SAT , MAX-SAT problem are example of NP-Complete problem.
Category 2: Non-polynomial running time Algorithm (NP Class)
A problem which have not worst case running time in polynomial form or let say super polynomial form or that can’t be solved in polynomial time that type algorithm will come under NP Class or Non-polynomial running time Algorithm Basically you can remember in this way A Problem which we can’t solve or by running it even huge amount of time is known as NP Class Problem .
Point Of Confusion:
Randomized quick-sort algorithm has running time in worst case O(N log N) is it belongs to Polynomial Running time or P class.
Q: In which class you will put this problem ?
Consider final examination scheduling. A school has n courses and five days in which to schedule examinations. An optimal schedule would be one where no student has to take two examinations on the same day. This seems like an easy problem. But there are O(5n) possible different schedules. If we looked at them all with a computer which could check a million schedules every second, the time spent checking for a value of n = 50 would be about
Thinking Question: State Whether You can Solve this problem
1) What is the fastest algorithm for multiplication of two n-digit numbers?
2) What is the fastest algorithm for matrix multiplication?
3) Can the graph isomorphism problem be solved in polynomial time?
Some More thoughts:
- The problems which have Yes or No answer are called decision Problem
- Problems that have an efficient algorithm to solve it are called decidable problems.
- Problems that can’t be solved with an algorithmm are called undecidable problems.
- The class of decision problems that can be solved by Non Deterministic machine in Polynomial time are called NP Problems.
- A Problem is said to be NP-Complete if it is contained in NP Class and all other problems in NP can polynomially reduced to it (NP Hard)
- A language is said to be NP Complte if L is in NP and for every language L` in NP there is a polynomial -time reduction of L` to L.
- If any NP-Complte problem is in P, then P = NP
Useful Resources : Here