Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We recall that a computable number $\alpha \in \mathbb{R}$ satisfies the following: there exists a computable function $f$ such that, given any positive rational error bound, $f$ outputs a rational number $q=f(\epsilon)$ satisfying $\vert \alpha -q \vert < \epsilon$.

Do there exist formulations of computability that provide definite bounds on the runtime of $f$? For example, one could ask for which real numbers $\alpha$ there exists a computable function $f$ that returns the first $n$ digits of $\alpha$ (or some equivalent accuracy, to solve the rounding problem) in $O(n)$ time.

My question is this: are there examples of computable numbers $\alpha$ for which it is known that no algorithm for computing $\alpha$ can return an $n$-digit approximation to $\alpha$ in $O(\phi(n))$ time, for fixed function $\phi$? Such numbers would be, intuitively, "provably difficult to compute."

share|improve this question
add comment

3 Answers

up vote 8 down vote accepted

The time hierarchy theorem shows how do construct subsets of $\mathbb N$ that are (almost) arbitrarily difficult to decide. If you take such a subset $A$ and define $\alpha$ to have its binary digits given by whether their positions are in $A$ or not, you have a number that is "provably difficult to compute".

share|improve this answer
add comment

You can indeed ask for bounds on the run time. In the area I am working in at the moment, this kind of requirement is used to define a convenient setting in which to state results. Two kinds of approximation are useful:

  • getting $n$ digits in polynomial time in $n$; for example this paper
  • getting $\log n$ digits in polynomial time in $n$; this requirement is equivalent to saying that $e^\alpha$ has a fully polynomial time approximation scheme or is "efficiently approximable"

To answer your last question: yes, the time hierarchy theorem will give you all the hard-to-compute functions you want.

share|improve this answer
add comment

Are you defining the number in terms of a given algorithm or its output? If the latter I suspect no such nontrivial number is known. See http://cstheory.stackexchange.com/questions/9840/what-are-some-problems-where-we-know-we-have-an-optimal-algorithm

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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