Understand Polynomial Vs Non-Polynomial Running time.

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

                       200,000,000,000,000,000,000 years!

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

Advertisements

One thought on “Understand Polynomial Vs Non-Polynomial Running time.

  1. Randomized quick-sort algorithm has running time in worst case O(N log N) is it belongs to Polynomial Running time or P class.
    Ans: The first is a class which contains all of the problems we solve using computers. If we think about the problems we actually present to the computer we note that not too many computations require more than O(n3) or O(n4) time. In fact, most of the important algorithms we compute are somewhere in the O(log n) to O(n3) range. Thus we shall state that practical computation resides within polynomial time bounds. There is a name for this class of problems.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s