1
$\begingroup$

I been reading Wikipedia for polynomial time, and it says:

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

My questions are:

  1. Why do we have addition and multiplication but no division?
  2. Why do we have both multiplication and addition, couldn't we express one with the other?
  3. What is the difference between polynomial time and exponential time by definition?
$\endgroup$
6
$\begingroup$

You seem to be struggling with a lot of the fundamental concepts, here. All the NP-completeness stuff is cool and fascinating and I can absolutely see why you're attracted to it. But you really aren't going to get anywhere with this stuff until you have a good grasp of the basics. If you want to work on NP-completeness, you need first to get a good book on basic discrete mathematics and you need to study it until you understand it. I know that's kind of dull but there is no other way. There might be a question here already about recommendations for discrete maths books.

This is a technical, precise subject where every little part of every little sentence has some special meaning. It's not like, say, the rules of some sport that you can pick up more or less just by watching people play. Yes, you can get a general, intuitive understanding of why, say, an NP-complete problem seems to be very hard to solve, in just the same way that you can get a general, intuitive understanding of how quantum tunnelling allows radioactive decay to happen. But, if you want to discover new things about it, you need to understand the underlying mathematics. There is no other way.


If all you want to do is talk about the running time of algorithms, you don't need to worry about polynomial expressions; just about polynomials. Polynomial expressions are generalizations of polynomials to be functions of things other than numbers. Over numbers (integers, reals, complex, anything else), the polynomials are the functions of the form $$f(x) = a_kx^k + a_{k-1}x^{k-1} + \dots + a_1x + a_0\,,$$ where $k$ is an integer constant and the $a_{i}$ are constants of the same kind of number as $x$ will be.

1. Why do we have addition and multiplication but not division?
The unhelpful answer is "Because that's the definition," just like CNF is defined using AND and OR rather than, say, XOR and NOR. The reason for forbidding division is that you might want to have a polynomial in a situation where division doesn't make sense (e.g., if you're working mod 2, or $x$ is an integer and you want to guarantee that $f(x)$ is also an integer). The kind of function you can make by dividing one polynomial by another is called a rational function and these are also widely studied and very useful in many situations. Why don't we use rational functions instead of polynomials in complexity theory? It's mostly because we don't need that level of detail: we already say that $4x^3 + 2x + 1$ is basically just some constant times $x^3$ so we wouldn't gain anything by bringing division to the party.

2. Why do we have both multiplication and addition, couldn't we express one with the other?
Because there's no way to express all the multiplications in a polynomial as repeated addition, while still keeping the form of a polynomial. Sure, you could write $3x$ as $x+x+x$ but that would be hard to read and wouldn't gain anything. But there's no way to write $x^2$ using a fixed number of additions: there's nothing in the definition of a polynomial that lets you write $$\underbrace{x + \dots + x}_{x \text{ times}}\,.$$

3. What is the difference between polynomial time and exponential time by definition?
An exponential function is one of the form $k^x$ for some constant $k$. Note that this is different to a polynomial: polynomials are "variable-to-the-constant" and exponentials are "constant-to-the-variable". Exponentials grow much faster than polynomials. For example, see this plot. As G. Bach points out in his comment, if you're defining complexity classes around exponential functions, you need to take $k>1$.

$\endgroup$
1
  • 2
    $\begingroup$ You can't use just any constant $k$ as the base for exponential time complexity, it needs to be $k>1$. $\endgroup$ – G. Bach Dec 8 '13 at 13:43
4
$\begingroup$

Note that the questions you're asking (apart from 3.) don't have anything to do with complexity theory, so you'll have to forget that mindset for a moment to understand what you read.

  1. Because polynomials are defined as sums of multiples of non-negative integer powers of variables.

  2. Because using both makes the expressions far smaller and easier to comprehend. One alternative would be to use recursive functions and those aren't exactly the most intuitive thing.

  3. $\mathcal{O}(n^k) \subsetneq \mathcal{O}(b^{(n^c)})$ for any $k \in \mathbb{R}, b>1, c > 0$. In words: any exponential function grows strictly faster than any polynomial function, asymptotically.

$\endgroup$
1
  • $\begingroup$ Tnx, how ever I don't understand 3, I will ask a new question about it. $\endgroup$ – Ilya Gazman Dec 8 '13 at 13:02
2
$\begingroup$
  1. We're mostly concerned with approximate bounds. If you know an upper bound, given by a rational function, you can write a shorter one, given by a polynomial. This doesn't mean that you can't, only that you don't need to.

  2. No, how?

  3. One is $n^k$, the other is $k^n$. Take $k=2$ and see how they compare.

$\endgroup$
6
  • $\begingroup$ Can you please give more detailed answer for 2. And can explain 3 in terms of definition just like it done in wiki for Polynomial time with polynomial expression. The answer that I am looking for 3 should not be referred to polynomial time definition. $\endgroup$ – Ilya Gazman Dec 8 '13 at 11:52
  • $\begingroup$ 2. You're probably thinking that $a+b = a \cdot (1 + \frac b a)$, but polynomials have an $x$ and there is no way to write $1+x$ without $+$ or $x^2$ without $\times$. $\endgroup$ – Karolis Juodelė Dec 8 '13 at 12:15
  • $\begingroup$ 3. It'w written in wikipedia, An algorithm is said to be exponential time, if $T(n)$ is bounded by $O(2^{n^k})$. What of this needs explaining? $\endgroup$ – Karolis Juodelė Dec 8 '13 at 12:19
  • $\begingroup$ 2: You can implement multiplication with addition only, like it done in high school. Or you can reduce both addition and multiplication to circuit sat $\endgroup$ – Ilya Gazman Dec 8 '13 at 12:22
  • $\begingroup$ You can't express multiplication as iterated addition because there's no mechanism for iteration. It's just a fixed expression. $\endgroup$ – David Richerby Dec 8 '13 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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