# Exponential time algorithms

Wiki define Polynomial time as fallow:

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., $T(n) = O(n^k)$ for some constant $k$

I understand that in general speaking the difference between Polynomial time and Exponential time is that exponential function grows strictly faster than any polynomial function, asymptotically(reference).

I am trying to understand the core definition of Exponential time.

1. What elements will make one algorithm to run in Exponential time?
2. What change do I need to do in the polynomial expression to make it Exponential time?(By it I am referring to the algorithm definition in the beginning of the question)
• 1. Do exponentially many things. 2. Use the polynomial as the power of a base > 1. Dec 8, 2013 at 13:19
• I don't understand your second question. Polynomials are polynomials; exponentials are exponentials. Asking what you need to change to make a polynomial into an exponential is like asking what you need to change to make a logarithm into a cosine. Dec 8, 2013 at 13:34
• @DavidRicherby Will there be exponential time functions if P = NP? How can you define an exponential time function in terms of polynomial expression? Dec 8, 2013 at 13:53
• Exponential functions will certainly still exist if P=NP. There are probably still problems that'll take exponential time even if P=NP, though none spring to mind immediately. An exponential function can be defined in terms of a polynomial, but that polynomial must be infinitely long - you may want to look up Taylor Expansions if you're interested in this. Dec 8, 2013 at 13:59
• @ymbirtt Even the easiest version of the time hierarchy theorem says that there is no polynomial-time algorithm for any EXPTIME-complete problem. That's an unconditional result: it doesn't depend on the assumption that P$\neq$NP. Dec 8, 2013 at 14:10

1. There's no easy answer for this one, though there are signs to look out for. Examining every possible subset of a set, for instance, is exponential - so if I had a set of integers $\{x_1,...,x_n\}$, and wanted to check every subset of these to see if they sum to $0$, I'd have to consider exactly $2^n$ subsets, which makes this method exponential time. Several different traps can make an algorithm exponential time, however, so rather than looking out for broad categories, analyse algorithms on a case-by-case basis.
2. If an algorithm takes $n^2$ steps to complete, then it's polynomial. If it takes $2^n$ steps, it's exponential. The difference is the position of the $n$. If something is $O(n^m)$ for $n> 1$, $m>0$, then it's polynomial in $n$ for fixed $m$, but exponential in $m$ for fixed $n$.
• Careful. The function $n^m$ isn't polynomial in $n$ unless $m$ is a constant. And, if $m$ is a constant, it doesn't make sense to say that the function is exponential in that constant. Dec 8, 2013 at 14:16
Often you get an exponential time brute-force algorithm when you consider a problem, and enumerate its whole search space. Typically, you'd think of subset problems (in SAT, you would choose a subset of variables set to true), permutation problems (in TSP, every tour is a permutation of the cities), and partition problems (in graph coloring, you are trying to partition the vertices into color classes). Or consider sorting even: there are $n!$ permutations of $n$ integers. Go through every permutation, and check if it is sorted. Silly (and slow), but it works.
• Though note that $O(n!)$ is even worse than $O(k^n)$. If you're still trying to learn about time complexity, this could be a useful thing to prove to yourself. Dec 8, 2013 at 13:40