# What infinite sums cannot be approximated in polynomial time?

The following is from the book Geometric algorithms and combinatorial optimization:

It shows an infinite sum that has an FPTAS (= an $$\epsilon$$-approximation can be computed using poly($$1/\epsilon$$) elements), and also a polynomial-time algorithm (= an $$\epsilon$$-approximation can be computed using poly($$\log(1/\epsilon)$$) elements).

This made me interested in what other infinite sums have or don't have an FPTAS or a polynomial-time algorithm (in the above sense). Specifically, what are some natural infinite sums for which no polynomial-time algorithm exists unless P=NP?

I thought the term Diophantine approximation is relevant, but did not find there any information about infinite series.

EDIT: to make the question more specific, I am looking for a function $$f$$ on natural numbers, such that

• $$f(k)$$ can be computed efficiently (e.g. using a constant number of arithmetic operations, or in time polynomial in $$\log(k)$$).
• The sum $$\sum_{k=1}^{\infty} f(k)$$ converges to some real number $$s$$.
• There is no algorithm that, for every rational number $$\epsilon>0$$, computes a rational number $$r$$ such that $$|s-r|<\epsilon$$, in time polynomial in $$\log(1/\epsilon)$$.
• Optional: there is even no such algorithm that runs in time polynomial in $$1/\epsilon$$.
• I guess you're asking for real numbers for which it not known how to compute their first n bits in poly(n) time, but it is known how to compute them in exp(n) time? Jan 31 at 19:29
• @RobinKothari real numbers for which it is provably impossible to compute their first n bits in poly(n) time, unless P=NP. Jan 31 at 19:31
• Take the $x\in(0,1)$ where the $i$th bit (in the fractional part) is $1$ if the $i$th TM (in any standard encoding) halts on empty input, and $0$ otherwise. Jan 31 at 21:14
• Regarding Diophantine approximation, there's the Flint Hills sequence, $\sum{\frac1{n^3\sin^2n}}$. It's unknown whether it converges, so in particular it can't be approximated Feb 1 at 4:28
• Let $f(n)=2^{-M}$ if $n=\langle M,1^t\rangle$ and the TM with code $M$ halts (on empty input) in exactly $t$ steps, and $f(n)=0$ otherwise. Then $f$ is poly-time computable, and the sum monotonically converges to a real between $0$ and $1$, which cannot be approximated by any algorithm at all (never mind its complexity). It's the Chaitin constant, basically. Feb 1 at 19:41

OP asks (now in the comments) for a real number $$s$$ such that (among other things), one can prove that, if the first $$n$$ bits of $$s$$ can be computed in time poly$$(n)$$, then P$$=$$NP. Perhaps the most obvious way to prove this would be to find a poly-time Turing reduction to the latter problem from some NP-hard problem.

We observe that such a reduction is unlikely to exist:

Lemma 1. If there is such a reduction, then the polynomial-time hierarchy collapses to $$\Delta_{2}^{P}$$.

Proof.

1. Fix any real number $$s$$. In what follows, by OP's problem, we mean the problem of computing the first $$n$$ bits of $$s$$ in time poly$$(n)$$, given $$n$$.

2. Define the decision problem $$D_s$$ as follows:

Decision problem $$D_s$$:
$$~~~$$ input : $$\omega\in \{0,1\}^*$$
$$~$$ output : Is $$\omega$$ a prefix of the binary representation of $$s$$?

1. OP's problem Turing-reduces in poly-time to $$D_s$$. (Indeed, given $$n$$, by calling a decision procedure for $$D_s$$ on one input of each length $$1, 2, \ldots, n$$, in a standard way, one can successively determine the first $$n$$ bits of $$s$$.)

2. So, if there is a poly-time Turing reduction to OP's problem from any NP-hard problem, then $$D_s$$ is NP-hard under Turing reductions.

3. However $$D_s$$ is a sparse language. (Indeed, it contains at most one word of any given size.)

4. Lemma 1 follows from Steps 4 and 5 by Mahaney's theorem. $$~~~\Box$$

Remarks. The lemma doesn't rule out proving the existence of such an $$s$$ by other means. Indeed, as observed in the comments, there are real numbers $$s$$ such that the problem of computing a given bit of $$s$$ (or approximating $$s$$ to an additive $$\epsilon$$) is undecidable. The takeaway is perhaps that we haven't quite yet pinned down a problem definition that captures what OP is after.

OP's problem is also in P/POLY (where we allow P/POLY to contain the functions that can be computed in polynomial time with polynomial advice, as opposed to languages).

OP also states the following (easier) variant of his problem:

Given $$\epsilon > 0$$, compute in time polylog($$1/\epsilon$$) a number $$r$$ such that $$|r-s| \le \epsilon$$.

This variant reduces to OP's problem (as defined at the top of this answer). Specifically, the first $$n$$ bits of $$s$$ approximate $$s$$ to within an additive $$O(2^{-n})$$. Hence, if there were a poly-time Turing reduction from any NP-hard problem $$\Pi$$ to this variant, there would also be a poly-time Turing reduction from the NP-hard problem to OP's problem as defined here. So, by the lemma, the poly-time hierarchy would collapse.

• So computing $r$ can be undecidable, but not NP-hard? This confused me at first, until I read this: cs.stackexchange.com/q/7676/1342 Feb 9 at 10:18
• Yes. E.g. there are many sparse undecidable languages. Indeed, any language can be made sparse by re-encoding it in unary, which increases the input size exponentially. This exponential increase makes no difference w.r.t. decidability, but of course makes a huge difference w.r.t. polynomial time. In fact, it is known that there is no sparse NP-hard language unless the polynomial hierarchy collapses. Similarly, any sparse language is in P/POLY, but P/POLY provably contains undecidable languages. Mar 28 at 14:57