5
$\begingroup$

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

enter image description here

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$.
$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ Jan 31 at 19:29
  • 1
    $\begingroup$ @RobinKothari real numbers for which it is provably impossible to compute their first n bits in poly(n) time, unless P=NP. $\endgroup$ Jan 31 at 19:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Jan 31 at 21:14
  • 1
    $\begingroup$ 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 $\endgroup$ Feb 1 at 4:28
  • 2
    $\begingroup$ 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. $\endgroup$ Feb 1 at 19:41

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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 $\endgroup$ Feb 9 at 10:18
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Mar 28 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.