2
$\begingroup$

EDIT: A more straightforward way of asking this question is: does evaluating a non-linear function require performing at least one multiplication?

ORIGINAL QUESTION:

I have an infinitely differentiable function f(x) which takes as input an $n$-bit integer $x$ and outputs a $kn$-bit integer, where $k$ is a contant. I know that $f(x)$ is not a linear function of $x$, and I want to argue that the complexity of evaluating $f$ on $x$ is at least $n \log n$.

I think this should be true, since I can write $f(x) = f(x_0) + f'(x_0)(x-x_0) + f''(x_0)(x-x_0)^2 + ...$ and computing $(x-x_0)^2$ requires at least $n \log n$ operations.

However, I don't think this ``proof by Taylor series" would yield a proof, and this would rule out smooth non-linear functions that have complexity $n \log \log n$, for instance.

Any suggestions on how to prove this / give a counterexample?

Thanks!

$\endgroup$
7
$\begingroup$

Note that proving that evaluation of $f$ takes at least as much time as integer multiplication only shows that it needs time $\Omega(M(n))$; while this is generally assumed to be at least $n\log n$, no superlinear bound has been proven. (However, I disagree that this wouldn’t yield anything nontrivial, as was formerly stated in Joshua Grochow’s answer. For one thing, there are plenty of analytic functions such as exp, log, sin where this $\Omega(M(n))$ bound is close to optimal up to one more logarithmic factor. For another thing, we normally regard a proof of NP-completeness of some problem as a strong evidence that it is hard, despite that with the current state of knowledge it doesn’t imply any superlinear lower bound either.)

As pointed out by Joshua Grochow, you cannot say anything useful about the complexity of evaluation of analytic functions at integers. The correct statement you are looking for is that approximation of smooth functions on short real intervals is at least as hard as integer multiplication. This indeed follows from Taylor expansion, though in full generality there are some messy details where the devil is (in particular, we a priori know nothing about the coefficients of the Taylor series).

As usual in this context, it is convenient to restrict attention to time bounds obeying some basic regularity conditions. Let me say that $T(n)$ is a reasonable bound if $T$ is nondecreasing, and $$c_1T(n)\le T(2n)\le c_2T(n)$$ for some constants $1<c_1\le c_2$. Commonly encountered bounds of polynomial growth involving powers of $n$, $\log n$, and similar, are all reasonable.

In order to avoid issues with representation of real numbers, we will only considered real functions on bounded intervals. An $n$bit approximation of $x$ is then a dyadic rational $x'$ written in the usual binary notation with $n$ bits after the radix point, such that $|x-x'|\le2^{-n}$. A function $f\colon[a,b]\to\mathbb R$ can be computed in time $T(n)$, if given a dyadic rational $x\in[a,b]$ with $n$ bits after the radix point, we can compute in time $T(n)$ an $n$bit approximation of $f(x)$.

Proposition: If $T$ is a reasonable bound, and $f\colon[u,v]\to\mathbb R$ (where $u<v$ are real) a nonlinear $C^3$ function that can be computed in time $T(n)$, then multiplication of $n$bit integers can be computed in time $O(T(n))$.

Proof:

Note that any Turing machine computing $f$ must read the whole input (at least for some inputs of every length $n$), thus we must have $T(n)\ge n$.

Since $f''(x)$ is continuous and not constantly $0$, we can find $x_0\in(u,v)$ of the form $x_0=k2^{-l}$ such that $f''(x_0)\ne0$. Since $f(x_0+x)$ is also computable in time $O(T(n))$, we can assume that $u<0<v$ and $f''(0)\ne0$. Likewise, $f(2^{-l}x)$ is computable in time $O(T(n))$ for fixed $l$, hence we may in fact assume $[u,v]=[-1,1]$.

By Taylor’s theorem, we have $$|a_0+a_1x+a_2x^2-f(x)|\le M|x|^3,\qquad x\in[-1,1],$$ for some constants $a_0,a_1,a_2,M\in\mathbb R$, where $a_2\ne0$. We can compute $f(x)-a_0$ in time $O(T(n))$ by subtracting an $(n+1)$bit approximation of $a_0=f(0)$ from an $(n+1)$bit approximation of $f(x)$, hence we can assume $a_0=0$.

Then we can also compute $a_1x$ in time $O(T(n))$ using a $(2n+m)$-bit approximation of $f(2^{-(n+m)}x)$, where $m$ is a suitable constant: we have $$|2^{n+m}f(2^{-(n+m)}x)-a_1x|\le|a_2|2^{-(n+m)}|x|^2+M2^{-2(n+m)}|x|^3 \le(|a_2|+M)2^{-(n+m)},$$ hence it is enough to take $m>\log_2(|a_2|+M)+1$. This means we can compute $f(x)-a_1x$, hence we can as well assume $a_1=0$.

Using the same trick once more, we have $$|2^{2(n+m)}f(2^{-(n+m)}x)-a_2x^2|\le M2^{-(n+m)},$$ hence we can compute $a_2x^2$ on $x\in[-1,1]$. By scaling, we can compute it on any fixed bounded interval, and we can also compute $$a_2xy=\tfrac14\bigl(a_2(x+y)^2-a_2(x-y)^2\bigr).$$ Now we need to get rid of the $a_2$ factor. Since $$xy=a_2x(a_2ya_2^{-2}),$$ it is enough to compute the constant $a_2^{-2}$ (meaning, given $n$ in unary, compute an $n$bit approximation of $a_2^{-2}$ in time $O(T(n))$). This can be done with Newton iteration: $a_2^{-2}$ is the unique root of the function $g(x)=1-(a_2^2x)^{-1}$. Thus, if $x_0$ is a suitable good appromixation to $a_2^{-2}$, the sequence given by $$x_{k+1}=x_k-\frac{g(x_k)}{g'(x_k)}=2x_k-a_2^2x_k^2=2x_k-a_2x_k(a_2x_k1)$$ converges quadratically to $a_2^{-2}$. In order to approximate $a_2^{-2}$ to $n$ bits, we need $O(\log n)$ iterations; the final iteration needs to be computed with $n$ bits of precision, the last but one with $n/2$ bits, and so on, hence the total time is linear in $$T(n)+T(n/2)+T(n/4)+\cdots\le(1+c_1^{-1}+c_1^{-2}+\cdots)T(n)=O(T(n)).$$ Thus, we can approximate $xy$ for $x,y\in[0,1]$ to $n$ bits of precision in time $O(T(n))$. Then we can multiply two $n$bit integers by scaling them to $[0,1]$, approximating the product, and scaling back.

$\endgroup$
  • $\begingroup$ In case it matters, one can relax $C^3$ to $C^{2,\alpha}$ for any constant $\alpha>0$ (that is, $f$ has a Hölder-continuous second derivative). $\endgroup$ – Emil Jeřábek supports Monica Sep 12 '14 at 17:53
  • $\begingroup$ I realized that $a_1=0$ may be arranged much more simply by replacing $f$ with $f(x)+f(-x)$. $\endgroup$ – Emil Jeřábek supports Monica Jul 5 '17 at 14:23
  • $\begingroup$ Also, the statement holds more generally for non-linear $C^{2,\alpha}$ functions from a nonempty open subset of $\mathbb R^n$ to $\mathbb R^m$. $\endgroup$ – Emil Jeřábek supports Monica Jul 5 '17 at 15:03
5
$\begingroup$

First, super-linear lower bounds on multiplying two integers are not known: for all we know, there may be an $O(n)$-time algorithm for multiplying two $n$-bit integers. So even if your "proof by Taylor series" idea worked, it wouldn't yield anything nontrivial a $\Omega(n \log n)$ lower bound, all it would yield is a lower bound of $\Omega(M(n))$ where $M(n)$ is the time to multiply two $n$-bit integers. (Thanks to Emil Jeřábek for pointing out that a $\Omega(M(n))$ lower bound need not be considered trivial, as there are many problems where it is very close to tight.)

Second, although you started with an infinitely differentiable function $f$ (presumably $f\colon \mathbb{R} \to \mathbb{R}$), since you are only talking about the complexity of evaluating it at integer points the fact that the function you started with was infinitely differentiable cannot be relevant. For given any function $h\colon \mathbb{Z} \to \mathbb{Z}$, there is an infinitely differentiable function $\widehat{h}\colon \mathbb{R} \to \mathbb{R}$ that agrees with $h$ on integer points. So the complexity of infinitely differentiable functions restricted to $\mathbb{Z}$ can be completely arbitrary (or, as arbitrary as the complexity of any integer function can be, which is pretty arbitrary).

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