Suppose I have the following double summation \begin{align} F(n) = \sum_{i = a}^{\lfloor f(a, n) \rfloor } \ \sum_{j = b}^{\lfloor g(a, b, i, n) \rfloor } 1 \qquad a,b,n \in \mathbb{N}, \end{align} where $\lfloor x \rfloor$ denotes the floor function (the greatest integer less than or equal to $x$) and where $f$ and $g$ are functions which depend only on their arguments and involve only a finite number of simple operations of arithmetic, i.e., addition, subtraction, multiplication, squaring and root extraction.

Question(s): Does it follow immediately that $F(n)$ is a polynomial-time algorithm? If not, how does one compute algorithmic complexity of such a function? Does the algorithmic complexity remain the same if we generalize $F$ to $N$ iterated summations of similar type?


Update: Suppose further that $f(a,n)$ and $g(a,b,i,n)$ do not grow too quickly as functions of $n$, say at most $O(\sqrt{n})$. For example, \begin{align} F(n) = \sum_{i = 0}^{\lfloor \sqrt{n} \rfloor } \ \sum_{j = 1}^{ \lfloor 2 \sqrt{2 n - i^{2}} \rfloor} 1. \end{align} Is $F(n)$ computable in polynomial time?

Clarification: I am not asking about the order of magnitude or any asymptotic of $F$ in terms of $n$. The question is about complexity. Sure, $F$ is a function, but I'd like to view it as an algorithm and determine whether the steps in computing its value $F(n)$ for a given integer $n$ can be done in polynomial time or otherwise.

  • $\begingroup$ I don't think so. Let f(a,n) := {if (n>1) n*f(a,n-1) else 1} = n!. Then f(a,n) is a polynomial-time algorithm using simple operations but F(n) is not a polynomial-time algorithm. $\endgroup$ – Apprentice Queue Apr 14 '11 at 18:47
  • $\begingroup$ Precisely what is the input? $\endgroup$ – András Salamon Apr 16 '11 at 23:49
  • $\begingroup$ An enormous integer $n$. $\endgroup$ – user02138 Apr 17 '11 at 15:53

I think you're confusing a few issues. Firstly, $F$ isn't an 'algorithm' in and of itself; it's a function. You can ask if $F$ is polynomially bounded, and whether there's a polynomial-time algorithm to compute $F$, but those two are different statements. I'm assuming that you're after polynomial boundedness - that is, that there's some polynomial $p(n)$ such that $F\in O(p(n))$ , but clarifying the question would be immensely useful.

The first thing to note is that the inner summation is trivial, and in fact the presence of 'b' as a lower summation limit is somewhat misleading; your formula works out to $F(n) = \Sigma_{i=a}^{f(a,n)}\left(g(a,b,i,n)-b\right)$ and it's easy to absorb the $-b$ term into the definition of $g$. Now, if $g$ is polynomially bounded in all its arguments, then its maximum over all $i$ in some polynomial range is also polynomially bounded as a function of $a$, $b$, and $n$; this is essentially the statement that polynomials are closed under composition, that is that if $p(n)$ is a polynomial and $q(n)$ is a polynomial, then $r(n)=p(q(n))$ is also a polynomial (and this extends to the multivariate case). So the sum (as a function of $a$, $b$, and $n$) is bounded by $f(a,n)$ times the maximum value of $g$ over the specified range, and thus is polynomially bounded.

Note that you need polynomial bounding in all the parameters for this argument to go through, and that 'polynomially computable' doesn't imply 'polynomially bounded'. For instance, ignoring the parameters $a$ and $b$ for a moment, it's easy to find $g(n,i) = n+2^i$ in time polynomial in $n$ and $i$, and it's even polynomially bounded as a function of $n$ for fixed values of $i$ - but then for something as simple as $f(n) = n$ the resulting sum isn't polynomially bounded (it grows exponentially with $n$).

Added on the clarification: with the clarified description, yes, it follows almost trivially that $F(n)$ is polynomial-time computable if $f$ and $g$ are polynomially bounded, for essentially the same reasons; seen from an algorithmic perspective, a polynomial-in-$n$ number of steps are executed a polynomial-in-$n$ number of times and by the composition theorem mentioned above the result is still polynomially bounded as a function of $n$. That's not necessarily useful, though, because for a problem of this nature what one would ideally like is to have a subpolynomially-bounded algorithm - for instance, things like multiplication can be easily done this way (choose $a=b=1$, $f(n)=n$, $g(n)=c$ to compute $F(n)=cn$) but one isn't usually interested in linear-time algorithms for multiplication! Ideally what you'd like is a polylogarithmic algorithm - something that can compute these sums in time $O(\log(n)^d)$ for some $d$ - and that's a much harder question, but I believe (without a specific example) that this can't be computed in polylogarithmic time; for instance, it shouldn't be hard to construct a reduction from this to something like the sum-of-square-roots problem.

  • $\begingroup$ Thanks for post. I don't think I'm confusing bounds with complexity. $\endgroup$ – user02138 Apr 14 '11 at 20:09
  • $\begingroup$ Also, your point about the triviality of the inner sum is not correct. Take for example, $a = b = 2$ and $f = n$ and $g = n - i$. The double sum (as stated) is zero for $n = 1, 2, 3$, while this is not the case for $\sum_{i = 2}^{\lfloor n \rfloor} (\lfloor n - i \rfloor - 2)$ or $\sum_{i = 2}^{\lfloor n \rfloor} (\lfloor n - i \rfloor - 1)$. $\endgroup$ – user02138 Apr 14 '11 at 20:16
  • $\begingroup$ @user02138: actually, I would claim that the double sum isn't uniquely defined in cases where the limits aren't correctly sorted, and there's a case to be made for it being negative! It preserves certain properties (linearity of the sum) that are handy to have. At any rate, this doesn't affect the computability of the sum at all, but now I'm confused about your motivations... $\endgroup$ – Steven Stadnicki Apr 14 '11 at 22:16

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.