the towers of hanoi problem takes exponential timethat isits running time is th( this is radically different from an algorithm that takes th( log ntime or th( time it is even radically different from problem that takes th( time these are all examples of polynomial running timebecause the exponents for all terms of these equations are constants recall from that if we buy new computer that runs twice as fastthe size of problem with complexity th( that we can solve in certain amount of time is increased by the fourth root of two in other wordsthere is multiplicative factor increaseeven if it is rather small one this is true for any algorithm whose running time can be represented by polynomial consider what happens if you buy computer that is twice as fast and try to solve bigger towers of hanoi problem in given amount of time because its complexity is th( )we can solve problem only one disk biggerthere is no multiplicative factorand this is true for any exponential algorithma constant factor increase in processing power results in only fixed addition in problemsolving power there are number of other fundamental differences between polynomial running times and exponential running times that argues for treating them as qualitatively different polynomials are closed under composition and addition thusrunning polynomial-time programs in sequenceor having one program with polynomial running time call another polynomial number of times yields polynomial time alsoall computers known are polynomially related that isany program that runs in polynomial time on any computer todaywhen transferred to any other computerwill still run in polynomial time there is practical reason for recognizing distinction in practicemost polynomial time algorithms are "feasiblein that they can run reasonably large inputs in reasonable time in contrastmost algorithms requiring exponential time are not practical to run even for fairly modest sizes of input one could argue that program with high polynomial degree (such as is not practicalwhile an exponential-time program with cost is practical but the reality is that we know of almost no problems where the best polynomial-time algorithm has high degree (they nearly all have degree four or less)while almost no exponential-time algorithms (whose cost is ( (cn )have their constant close to one so there is not much gray area between polynomial and exponential time algorithms in practice for the rest of this we define hard algorithm to be one that runs in exponential timethat isin ohm(cn for some constant definition for hard problem will be presented in the next section