8
$\begingroup$

Here are four tenets I cannot reconcile:

I feel I am missing some subtlety relating to the definition of an exponential-time algorithm as running in $O(2^{\mathrm{poly}(n)})$ rather than $O(2^{n})$, but I am not sure precisely where the subtlety lies.

$\endgroup$
  • 1
    $\begingroup$ I've edited the tags and tile since, really, this question has nothing to do with complexity theory: it's about mathematical notation and the asymptotic behaviour of mathematical functions. $\endgroup$ – David Richerby Jul 21 '18 at 15:15
25
$\begingroup$

The issue comes down to ambiguous terminology.

$(a^b)^c = a^{bc}$, but $a^{(b^c)} \neq a^{bc}$. In other words, exponents aren't associative.

Conventionally, nested exponentials without parentheses are grouped in this second way, because it's more useful. So $2^{2^n} = 2^{(2^n)} \neq 2^{2n}$. If we wanted to talk about $(2^2)^n$, we could just write $2^{2n}$ instead, so we reserve the double exponential notation for the other case.

$\endgroup$
  • 3
    $\begingroup$ That convention is the only sensible one. As you described choosing the other way of grouping would be useless since we could already express that value/function using $a^{b\cdot c}$ instead of a fancy "double exponential". $\endgroup$ – Bakuriu Jul 20 '18 at 21:24
  • 1
    $\begingroup$ @Bakuriu Oh, indeed, though it's important to note that it is just a convention. (There could also be the convention to always use parentheses, which is what LaTeX does: it refuses to guess how to group a^b^c, and throws an error instead.) $\endgroup$ – Draconis Jul 21 '18 at 3:04
  • 1
    $\begingroup$ All notation is "just a convention". Describing "$a^{b^c}=a^{(b^c)}$" as "just a convention" suggests that there are other plausible alternatives but, really, there aren't. $\endgroup$ – David Richerby Jul 21 '18 at 15:14
  • 1
    $\begingroup$ @DavidRicherby Certainly, all notation is conventional! But that doesn't mean it's not worth noting. It's a deliberate choice by mathematicians to use that notation: and it's a good choice, because it eliminates ambiguity and is more useful than the alternative. But it's still a choice, and nothing stops you from defining it differently (besides confusing readers for no real gain). $\endgroup$ – Draconis Jul 21 '18 at 16:45
  • 2
    $\begingroup$ @Bakuriu I wouldn't go so far as to say it's the only sensible convention, because it seems to me very sensible to assume that all operations are evaluated left-to-right, unless there are parentheses. That's what we do with addition and subtraction and what kids learn in grade school with "PEMDAS". The fact that exponentiation doesn't follow the convention has tripped up me in the past, and just about everyone who first learns about it. $\endgroup$ – 6005 Jul 22 '18 at 5:45
16
$\begingroup$

$a^{(b^c)}$ is not the same as $(a^b)^c$. When people write $2^{2^k}$, they usually mean $2^{(2^k)}$, not $(2^2)^k$.

$\endgroup$

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.