3
$\begingroup$

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)
Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 1. Do exponentially many things. 2. Use the polynomial as the power of a base > 1. $\endgroup$
    – G. Bach
    Dec 8, 2013 at 13:19
  • $\begingroup$ 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. $\endgroup$
    – David Richerby
    Dec 8, 2013 at 13:34
  • $\begingroup$ @DavidRicherby Will there be exponential time functions if P = NP? How can you define an exponential time function in terms of polynomial expression? $\endgroup$
    – Ilya Gazman
    Dec 8, 2013 at 13:53
  • $\begingroup$ 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. $\endgroup$
    – ymbirtt
    Dec 8, 2013 at 13:59
  • 2
    $\begingroup$ @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. $\endgroup$
    – David Richerby
    Dec 8, 2013 at 14:10

2 Answers 2

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – David Richerby
    Dec 8, 2013 at 14:16
  • $\begingroup$ Yes, you're right. I'll clarify that. $\endgroup$
    – ymbirtt
    Dec 8, 2013 at 14:17
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – ymbirtt
    Dec 8, 2013 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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