Exponential time algorithms

Question

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)

• G. Bach: 1. Do exponentially many things. 2. Use the polynomial as the power of a base > 1.
• David Richerby: 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.
• Ilya Gazman: @DavidRicherby Will there be exponential time functions if P = NP? How can you define an exponential time function in terms of polynomial expression?
• ymbirtt: 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.
• David Richerby: @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.

Answer 1

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$.

• David Richerby: 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.
• ymbirtt: Yes, you're right. I'll clarify that.

Answer 2

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.

• ymbirtt: 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.