Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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)
share|improve this question
2  
1. Do exponentially many things. 2. Use the polynomial as the power of a base > 1. –  G. Bach Dec 8 '13 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. –  David Richerby Dec 8 '13 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? –  Ilya_Gazman Dec 8 '13 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. –  ymbirtt Dec 8 '13 at 13:59
2  
@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. –  David Richerby Dec 8 '13 at 14:10

2 Answers 2

up vote 7 down vote accepted
  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$.

share|improve this answer
    
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. –  David Richerby Dec 8 '13 at 14:16
    
Yes, you're right. I'll clarify that. –  ymbirtt Dec 8 '13 at 14:17

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.

share|improve this answer
    
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. –  ymbirtt Dec 8 '13 at 13:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.