What is the intuition behind Polynomial Time?

 An algorithm is said to be solvable in Polynomial time (meaning solvable in a polynomial running time) if the number of steps involved in the algorithm can be expressed as :

where n is the complexity of input &

k is a non negative number.

Many problems we use in day-to-day life s.a. addition, subtraction, multiplication, division. power, logarithm etc are solvable in polynomial time.

Algorithms which require an exponential run time are said to be of not-polynomial time.


For curious ones: 

In order to solve any problem we devise some algorithm. different algo takes different time to execute. Problems can be classified in various ways such as Decision problems (Yes/No types), Search problems(such as finding factors of a number), Counting problems (how many primes are there between 50 & 500), Optimization problems ( s.a. Minimum/maximum time taken to solve a Rubik's cube) etc. 

If a problem is algorithmic and computable, being able to produce a solution may depend on the size of the input or the limitations of the hardware used to implement it. If a problem takes reasonable time for solution it is said to be Tractable & belong to P class problem (Polynomial time). if a problem takes unreasonably long time to get to a solution then we call it to be an NP class problem (could be Non-Deterministic Polynomial time) or Intractable Problem.



There is another concept called "Heuristic Algorithm". A heuristic algorithm is an algorithm that produces usable solutions to a problem in reasonable (polynomial) time. These solutions may not be proven to be optimal or even formally correct, they can however produce good solutions to the problem. Heuristic algorithms are based on the value of knowledge, experience and judgement in solving intractable problems. We can call it an educated/informed guess.

0 Comments