Skip to main content
MathOverflow

Return to Answer

added 2490 characters in body
Source Link
Noah Schweber
Noah Schweber
  • 21.1k
  • 10
  • 110
  • 331

Any noncomputableEDIT: This was in a comment below, but I now think it should be part of the main answer:

There are two different ways to ask the question in the OP:

  • Is there a real number $r$ such that no polytime algorithm computes all the bits of $r$?

  • Is there a real number $r$ such that no individual bit of $r$ can be computed by a polytime algorithm?

The former is the question I answer below; the latter is trivial! Given any real $r$, and any $n$, there is a polytime (indeed, constant time) algorithm $p_{r, n}$ which computes the first $n$ bits of $r$ correctly. (Consider the silly algorithm which has the string $\langle r(0), r(1), . . . , r(n)\rangle$" "hard-coded" in - on input $k$ for $k\le n$ this algorithm outputs $r(k)$, and on input $k$ for $k>n$ it outputs $0$ (say).) So in order to get anything interesting, we need to look at algorithms which attempt to compute all the bits simultaneously.

Note that noncomputable reals trivially satisfies yoursatisfy the first question., so the right question to ask is:

Is there a computable real number $r$ such that no polytime algorithm computes all the bits of $r$?

Here's an explicit construction of a computablecomputable real which is hard to compute:

Note that nothing special about polynomials was used here: given any reasonable complexity class (for instance, any complexity class of the form "Running time bounded by some $f\in\mathcal{F}$" for $\mathcal{F}$ a computable set of computable total functions), there is a computable real whose bits are not computable by any algorithm in that class.

Going back to the second, "trivial" version of the question, it can actually be "de-trivialized" in an interesting way: look at how hard it is to get successively longer approximations to $r$. That is, the silly algorithm I describe which gets the first $n$ bits correctly has length $\approx 2^n$; can we do better?

This question forms the basis of Kolmogorov complexity. Roughly speaking, given a real $r$, let $K^r$ be the function whose $n$th value is the length of the shortest Turing machine which computes the first $n$ bits of $r$ correctly. Then we can ask (even for noncomputable $r$!): how quickly does $K^r$ grow? If $r$ is computable, then $K^r$ is eventually constant; if $r$ is not computable, however, things get really interesting. (See e.g. the notion of K-trivials, which are reals which are "almost computable" in the sense of Kolmogorov complexity.)

Now, this isn't quite what you're asking about - you'd want to look at $K_{poly}^r$, the function whose $n$th value is the length of the least polytime Turing machine which computes the first $n$ bits of $r$ correctly. This, and other resource-bounded variations of Kolmogorov complexity, don't appear to be as studied - but see this article.

Any noncomputable real trivially satisfies your question. Here's an explicit construction of a computable real which is hard to compute:

Note that nothing special about polynomials was used here: given any reasonable complexity class (for instance, any complexity class of the form "Running time bounded by some $f\in\mathcal{F}$" for $\mathcal{F}$ a computable set of computable total functions), there is a computable real whose bits are not computable by any algorithm in that class.

EDIT: This was in a comment below, but I now think it should be part of the main answer:

There are two different ways to ask the question in the OP:

  • Is there a real number $r$ such that no polytime algorithm computes all the bits of $r$?

  • Is there a real number $r$ such that no individual bit of $r$ can be computed by a polytime algorithm?

The former is the question I answer below; the latter is trivial! Given any real $r$, and any $n$, there is a polytime (indeed, constant time) algorithm $p_{r, n}$ which computes the first $n$ bits of $r$ correctly. (Consider the silly algorithm which has the string $\langle r(0), r(1), . . . , r(n)\rangle$" "hard-coded" in - on input $k$ for $k\le n$ this algorithm outputs $r(k)$, and on input $k$ for $k>n$ it outputs $0$ (say).) So in order to get anything interesting, we need to look at algorithms which attempt to compute all the bits simultaneously.

Note that noncomputable reals trivially satisfy the first question, so the right question to ask is:

Is there a computable real number $r$ such that no polytime algorithm computes all the bits of $r$?

Here's an explicit construction of a computable real which is hard to compute:

Note that nothing special about polynomials was used here: given any reasonable complexity class (for instance, any complexity class of the form "Running time bounded by some $f\in\mathcal{F}$" for $\mathcal{F}$ a computable set of computable total functions), there is a computable real whose bits are not computable by any algorithm in that class.

Going back to the second, "trivial" version of the question, it can actually be "de-trivialized" in an interesting way: look at how hard it is to get successively longer approximations to $r$. That is, the silly algorithm I describe which gets the first $n$ bits correctly has length $\approx 2^n$; can we do better?

This question forms the basis of Kolmogorov complexity. Roughly speaking, given a real $r$, let $K^r$ be the function whose $n$th value is the length of the shortest Turing machine which computes the first $n$ bits of $r$ correctly. Then we can ask (even for noncomputable $r$!): how quickly does $K^r$ grow? If $r$ is computable, then $K^r$ is eventually constant; if $r$ is not computable, however, things get really interesting. (See e.g. the notion of K-trivials, which are reals which are "almost computable" in the sense of Kolmogorov complexity.)

Now, this isn't quite what you're asking about - you'd want to look at $K_{poly}^r$, the function whose $n$th value is the length of the least polytime Turing machine which computes the first $n$ bits of $r$ correctly. This, and other resource-bounded variations of Kolmogorov complexity, don't appear to be as studied - but see this article.

Source Link
Noah Schweber
Noah Schweber
  • 21.1k
  • 10
  • 110
  • 331

Any noncomputable real trivially satisfies your question. Here's an explicit construction of a computable real which is hard to compute:

Let $\{\varphi_e\}$ list all (partial) computable functions, and $\{p_e\}$ all polynomials.

We define a real number $r$ as follows: the $n$th bit of the binary expansion of $r$ is a $1$ iff $\varphi_i(n)$ does not halt and output $1$ in $\le p_j(n)$ steps (so, either doesn't halt in that time, or does halt and outputs something $\not=1$) - where $n=\langle i, j\rangle$. (Here "$\langle\cdot,\cdot\rangle$" denotes the Cantor pairing function.)

$r$ is computable (note that we run each computable function for only a bounded amount of time before deciding what to do for that bit), but $r$ is not computable in polynomial time since it diagonalizes against all polynomial-time computations: if $\varphi_i$ has running time bounded by $p_j$, then $\varphi_i(\langle i, j\rangle)\not=r(\langle i, j\rangle)$.

Note that nothing special about polynomials was used here: given any reasonable complexity class (for instance, any complexity class of the form "Running time bounded by some $f\in\mathcal{F}$" for $\mathcal{F}$ a computable set of computable total functions), there is a computable real whose bits are not computable by any algorithm in that class.