# Exponential Running Time – Intro to Algorithms

It turns out the answer is no, not all problems have efficient algorithms. They are some that actually require an exponential amount of running time. For example, an algorithm may have a bound of Î¸(2â ż). So an n gets larger, this is getting larger and larger and larger very very quickly. So this is considered not efficient. We’re going to talk in this course about any other problems that have provable lower bounds that are exponential that is to say that there can be no polynomial time solution to them. There is one in the literature, which is a generalization of checkers that you can learn more about if you take a course in complexity. But what I would like to talk about is this sort of funny gap between the problems that we know have efficient solutions that have polynomial running time, and the problems that we know do not have efficient solutions. They have the fastest algorithms that could run for them have to take of this exponential time. Then in between here there’s a gap. There’s actually some very very important problems that we don’t know whether they have a polynomial time solution of if they require exponential time. They are just kind off hovering in this no man’s land. The great unknown. There’s lot of different kinds of classes of problems that live in this gap, but I’m going to focus on for this unit is a class of problems known as the NP complete problems. They are not the only problems that fall in here, but they are very important class and probably the best studied class of problems that actually fall in this gap where we just don’t know if they are polynomial or exponential running time, and it’s really frustrating that we don’t know where this problems lie, but we do know something, and that is for all the NP complete problems either they are all easy and they fit in the polynomial running time class or they are all hard and they fit in the exponential time running class. We don’t know which it is, but we do know that they can all be hang together, and so sometimes it’s very useful if your studying a problem to discover whether it belongs to this funny class of NP complete problems that fit in the gap, so that’s what we’re going to take a look at.