<p>OP asks (now in the comments) for a real number <span class="math-container">$s$</span> such that (among other things), one can prove that, if the first <span class="math-container">$n$</span> bits of <span class="math-container">$s$</span> can be computed in time poly<span class="math-container">$(n)$</span>, then P<span class="math-container">$=$</span>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.</p>
<p>We observe that such a reduction is unlikely to exist:</p>
<p><strong>Lemma 1.</strong> <em>If there is such a reduction, then the polynomial-time hierarchy collapses to <span class="math-container">$\Delta_{2}^{P}$</span>.</em></p>
<p><em>Proof.</em></p>
<ol>
<li><p>Fix any real number <span class="math-container">$s$</span>.
In what follows, by <em>OP's problem</em>, we mean the problem of
computing the first <span class="math-container">$n$</span> bits of <span class="math-container">$s$</span> in time poly<span class="math-container">$(n)$</span>, given <span class="math-container">$n$</span>.</p>
</li>
<li><p>Define the decision problem <span class="math-container">$D_s$</span> as follows:</p>
</li>
</ol>
<blockquote>
<p>Decision problem <span class="math-container">$D_s$</span>:<br />
<span class="math-container">$~~~$</span> <strong>input :</strong> <span class="math-container">$\omega\in \{0,1\}^*$</span><br />
<span class="math-container">$~$</span> <strong>output :</strong> Is <span class="math-container">$\omega$</span> a prefix of the binary representation of <span class="math-container">$s$</span>?</p>
</blockquote>
<ol start="3">
<li><p>OP's problem Turing-reduces in poly-time to <span class="math-container">$D_s$</span>.
(Indeed, given <span class="math-container">$n$</span>, by calling a decision procedure for <span class="math-container">$D_s$</span>
on one input of each length <span class="math-container">$1, 2, \ldots, n$</span>, in a standard way,
one can successively determine the first <span class="math-container">$n$</span> bits of <span class="math-container">$s$</span>.)</p>
</li>
<li><p>So, if there is a poly-time Turing reduction to OP's problem from any NP-hard problem, then <span class="math-container">$D_s$</span> is NP-hard under Turing reductions.</p>
</li>
<li><p>However <span class="math-container">$D_s$</span> is a <em>sparse</em> language.
(Indeed, it contains at most one word of any given size.)</p>
</li>
<li><p>Lemma 1 follows from Steps 4 and 5 by <a href="https://en.wikipedia.org/wiki/Mahaney%27s_theorem" rel="nofollow noreferrer">Mahaney's theorem</a>. <span class="math-container">$~~~\Box$</span></p>
</li>
</ol>
<hr />
<p><strong>Remarks.</strong>
The lemma doesn't rule out proving the existence of such an <span class="math-container">$s$</span> by other means.  Indeed, as observed in the comments,
there are real numbers <span class="math-container">$s$</span> such that the problem of computing a given bit of <span class="math-container">$s$</span> (or approximating <span class="math-container">$s$</span> to an additive <span class="math-container">$\epsilon$</span>) is undecidable.  The takeaway is perhaps that we haven't quite yet pinned down a problem definition that captures what OP is after.</p>
<p>OP's problem is also in P/POLY
(where we allow P/POLY to contain the <em>functions</em> that can be computed in polynomial time with polynomial advice,
as opposed to <em>languages</em>).</p>
<p>OP also states the following (easier) variant of his problem:</p>
<blockquote>
<p><em>Given <span class="math-container">$\epsilon &gt; 0$</span>, compute in time polylog(<span class="math-container">$1/\epsilon$</span>) a number <span class="math-container">$r$</span> such that <span class="math-container">$|r-s| \le \epsilon$</span>.</em></p>
</blockquote>
<p>This variant reduces to OP's problem (as defined at the top of this answer).
Specifically, the first <span class="math-container">$n$</span> bits of <span class="math-container">$s$</span> approximate <span class="math-container">$s$</span>
to within an additive <span class="math-container">$O(2^{-n})$</span>.
Hence, if there were a poly-time Turing reduction
from any NP-hard problem <span class="math-container">$\Pi$</span> 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.</p>

CC BY-SA 4.0
2024-02-09T10:18:40.247Z
So computing $r$ can be undecidable, but not NP-hard? This confused me at first, until I read this: https://cs.stackexchange.com/q/7676/1342
Erel Segal-Halevi
CC BY-SA 4.0
2024-03-28T14:57:55.910Z
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.
Neal Young
CC BY-SA 4.0
2024-02-08T01:10:33.800Z
2024-02-08T01:37:23.527Z
2024-02-08T01:37:23.527Z
Neal Young
<p>The following is from the book <a href="https://link.springer.com/book/10.1007/978-3-642-78240-4" rel="nofollow noreferrer">Geometric algorithms and combinatorial optimization</a>:</p>
<p><a href="https://i.sstatic.net/Do334.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Do334.png" alt="enter image description here" /></a></p>
<p>It shows an infinite sum that has an FPTAS (= an <span class="math-container">$\epsilon$</span>-approximation can be computed using poly(<span class="math-container">$1/\epsilon$</span>) elements), and also a polynomial-time algorithm (= an <span class="math-container">$\epsilon$</span>-approximation can be computed using poly(<span class="math-container">$\log(1/\epsilon)$</span>) elements).</p>
<p>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?</p>
<p>I thought the term <a href="https://en.wikipedia.org/wiki/Diophantine_approximation" rel="nofollow noreferrer">Diophantine approximation</a> is relevant, but did not find there any information about infinite series.</p>
<p>EDIT: to make the question more specific, I am looking for a function <span class="math-container">$f$</span> on natural numbers, such that</p>
<ul>
<li><span class="math-container">$f(k)$</span> can be computed efficiently (e.g. using a constant number of arithmetic operations, or in time polynomial in <span class="math-container">$\log(k)$</span>).</li>
<li>The sum <span class="math-container">$\sum_{k=1}^{\infty} f(k)$</span> converges to some real number <span class="math-container">$s$</span>.</li>
<li>There is no algorithm that, for every rational number <span class="math-container">$\epsilon&gt;0$</span>, computes a rational number <span class="math-container">$r$</span> such that <span class="math-container">$|s-r|&lt;\epsilon$</span>, in time polynomial in <span class="math-container">$\log(1/\epsilon)$</span>.</li>
<li>Optional: there is even no such algorithm that runs in time polynomial in <span class="math-container">$1/\epsilon$</span>.</li>
</ul>

CC BY-SA 4.0
2024-01-31T19:29:41.057Z
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?
Robin Kothari
CC BY-SA 4.0
2024-01-31T19:31:50.510Z
@RobinKothari real numbers for which it is provably impossible to compute their first n bits in poly(n) time, unless P=NP.
Erel Segal-Halevi
CC BY-SA 4.0
2024-01-31T21:14:51.163Z
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.
Neal Young
CC BY-SA 4.0
2024-02-01T04:28:16.007Z
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
Command Master
CC BY-SA 4.0
2024-02-01T17:52:10.660Z
@NealYoung I should probably ask a more specific question; please see my edit.
Erel Segal-Halevi
CC BY-SA 4.0
2024-02-01T19:41:17.040Z
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.
Emil Jeřábek
CC BY-SA 4.0
2024-02-01T19:42:34.120Z
What's the model of computation?  Standard TM?  Real RAM?
Neal Young
CC BY-SA 4.0
2024-02-02T08:00:48.313Z
@NealYoung both are interesting
Erel Segal-Halevi
CC BY-SA 4.0
2024-02-02T14:03:31.123Z
The constraint "time polynomial in $\log k$" seems toothless.  E.g. suppose for a given $f$ that $f(k)$ is computable only in time $2^{2^k}$.   One could replace $f$ by $g$ such that $g(i) = f(k)$ when $i = 2^{2^k}$ for some integer $k$, and $g(i) = 0$ otherwise.  Then the sum doesn't change (as $\sum_i g(i) = \sum_k f(k))$, while $g(i)$ is computable in time $O(\log i)$.
Neal Young
<reference-request><approximation-algorithms><na.numerical-analysis><computing-over-reals>
What infinite sums cannot be approximated in polynomial time?
Erel Segal-Halevi
# What infinite sums cannot be approximated in polynomial time?

(Asked by: username_0 on 2024-01-31)

The following is from the book [Geometric algorithms and combinatorial optimization](https://link.springer.com/book/10.1007/978-3-642-78240-4):

[![enter image description here](https://i.sstatic.net/Do334.png)](https://i.sstatic.net/Do334.png)

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](https://en.wikipedia.org/wiki/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$.

**Tags:** reference-request, approximation-algorithms, na.numerical-analysis, computing-over-reals

> **Comments:**
> **username_1**: 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?  
> **username_0**: @RobinKothari real numbers for which it is provably impossible to compute their first n bits in poly(n) time, unless P=NP.  
> **username_2**: 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.  
> **username_3**: 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  
> **username_0**: @NealYoung I should probably ask a more specific question; please see my edit.  
> **username_4**: 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.  
> **username_2**: What's the model of computation?  Standard TM?  Real RAM?  
> **username_0**: @NealYoung both are interesting  
> **username_2**: The constraint "time polynomial in $\log k$" seems toothless.  E.g. suppose for a given $f$ that $f(k)$ is computable only in time $2^{2^k}$.   One could replace $f$ by $g$ such that $g(i) = f(k)$ when $i = 2^{2^k}$ for some integer $k$, and $g(i) = 0$ otherwise.  Then the sum doesn't change (as $\sum_i g(i) = \sum_k f(k))$, while $g(i)$ is computable in time $O(\log i)$.  

---

## 1 answers

### Answer by username_2 on 2024-02-08. Score: 1 | Accepted answer

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

3. 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$.)
4. 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.
5. However $D\_s$ is a *sparse* language.
   (Indeed, it contains at most one word of any given size.)
6. Lemma 1 follows from Steps 4 and 5 by [Mahaney's theorem](https://en.wikipedia.org/wiki/Mahaney%27s_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.

> **Comments:**
> **username_0**: So computing $r$ can be undecidable, but not NP-hard? This confused me at first, until I read this: https://cs.stackexchange.com/q/7676/1342  
> **username_2**: 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.  

---

