32
It is easy to get confused about what it means to "represent" or "implement" a real number. In fact, we are witnessing a discussion in the comments where the representation is contentious. So let me address this first.
How do we know that an implementation is correct?
The theory which explains how to represent things in a computer is realizability. The ...
19
Q1. This is a notorious open problem. It is known to be in the fourth level of the counting hierarchy, due to [ABKM]. Not known to be in NP. The problem is not really in computing square roots as claimed in the lecture notes: $n$ bits of a square root of an integer can be computed in time polynomial in $n$ and the bitsize of the integer. The problem is, ...
17
I work in real-number computation, and I wish I knew the real answer. But I can speculate. It's a sociological problem, I think.
The community of people who work on exact real arithmetic consists of theoreticians who are not used to developing software. So they usually relegate the task of implementation to students (a notable exception is Norbert Müller's ...
16
The real numbers may be characterized in a couple of ways, let us work with the Cauchy-complete archimedean ordered field. (We need to be a bit careful how exactly we say this, see Definition 11.2.7 and Defintion 11.2.10 of the HoTT book.)
The following theorem is valid in any topos (a model of higher-order intuitionistic logic):
Theorem: There is a ...
13
I am not exactly sure what the question is here, but I can try to say a bit to clean up possible misunderstandings.
First of all, if we are talking about complexity of a map $f : \mathbb{R} \to \mathbb{R}$, it makes no sense to ask "What is a good representation for $\sqrt{2}$?" Instead, you have to ask "What is a good representation for all inputs of $f$?"....
10
In general, people always care about floating point errors. However I disagree with Andrej, and I do not think that floats are preferred to arbitrary precision reals (for the most part) because of sociological reasons.
I believe the main argument against exact computation of reals is one of performance. So the short answer is, whenever performance is more ...
10
Blum, Shub and Smale created their model based on known algebraic models of computations, to unify (as much as possible) complexity theory and numerical analysis (cf. [1]). They wanted to give solid theoretical foundations to numerical analysis, and they wanted uniformity since the algorithms used in real life are uniform. Also, their model is a ...
10
Assuming a real is given as a sequence of rational approximations with the error bounded by some known computable function which tends to zero (all such approximations are equivalent, and correspond to the usual topology on the reals).
Computable functions are continuous. IsRational and IsInteger are not continuous and therefore not computable.
IsInteger ...
10
I tend to think this is undecidable:
Let $x$ be a computable irrational number.
Consider a TM $M$. You can construct a function that runs $M$ on $\epsilon$, and in parallel computes $x$ with growing precision.
If $M$ halts, it stops computing $x$, otherwise it continues.
Deciding if this function computes a rational number is equivalent to the halting ...
8
Brockett [1] studied a closely related idea, and showed how to construct dynamical systems that solve any linear programming problem in (I believe) the same manner you suggest, as well as dynamical systems to sort a list of numbers and to diagonalize a matrix. You may be able to use this to directly get the dynamics you need to compute the squaring function.
...
8
Depending on which version of $\mathsf{NP}_{\mathbb{R}}$ you use, yes or it's open. When one considers BSS machines that only use addition and subtaction, and only branch on equality, the answer is yes. If one includes branching on $<$, I believe it is still open, and the same if one allows multiplications. For details, see Cucker, Koiran, and Matamala "...
6
To answer my own question: for the purposes of exact computation, there's no need to worry about having too much computational power from linear combinations of algebraic numbers.
Details
On representations of algebraic numbers.
If the coefficients of all of the gates in a unitary circuit $U_n$ belong to a field extension $\mathbb E{:}\mathbb Q$ of finite ...
6
It is undecidable whether a given computable number is equal to zero.
(So your rational approximation oracle returns 0 for every ε you've tried? Maybe you just haven't given it a small enough ε.)
Thus, it's undecidable whether a given computable number between -½ and +½ is an integer.
5
Yes. Each time your $\sf NP$ machine want to query the $\sf PosSLP$ oracle, simply simulate the polynomial time oracle Turing machine underlying the inclusion $\sf PosSLP \subseteq {P}^{{PP}^{PP^{PP}}}$, passing its oracle queries to the $\sf {PP}^{PP^{PP}}$ oracle.
answered Jun 21 '12 at 11:05
Kristoffer Arnsfelt Hansen
3,9052 gold badges22 silver badges34 bronze badges
4
It's funny you should ask, because computability and diophantine approximation has actually been a popular topic in recent years. In particular Becher and Slaman and coauthors have many results and papers. See for instance
Becher, Verónica; Reimann, Jan; Slaman, Theodore A., Irrationality exponent, Hausdorff dimension and effectivization, ZBL06837203.
3
You wrote:
On the other hand there is this paper by Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 saying it is NP-complete, which also means it is in NP. Although he doesn't prove it in the paper, I think he consider the membership in NP trivial, as is usually the case with such problems.
Why don't you simply read the ...
3
Another model possibly to explore, is that of the Feasible RAM model. This is a modified real RAM model for Real computation, Feasible RAM, or a modified RAM model which uses both the discrete, and real valued arithmetic operations. This model allows for real, and discrete operations, and the Turing model, is interchangeable with it. The Feasible RAM model ...
3
As written, the problem requires time $2^{\Omega(m)}$, where $m$ is the length of input (you unfortunately used $n$ for something else). Indeed, if e.g. $\alpha$ is a positive integer (given by its minimal polynomial $x-\alpha$) and $n=0$, the size of the output is exponential in the size of the input. This bound is of course optimal, as there are a number ...
3
I think the answer is no, assuming $\mathsf{P}_{\mathbb{R}} \neq \mathsf{NP}_{\mathbb{R}}$ (I believe I give a proof below, but there are enough potentially nitpicky definitional issues here that I'm being cautious about my claims).
Proof that the answer is no assuming $\mathsf{P}_\mathbb{R} \neq \mathsf{NP}_{\mathbb{R}}$: In fact, I believe the following ...
2
A function being computable is a stronger than the function being continuous, i.e. any computable function needs to be continuous in the information topology.
You want to see if the function $F:\mathbb{R} \to \{Yes,No\}$ defined by
$$
F(r) =
\begin{cases}
YES & r\in \mathbb{Q}\\
NO & o.w.
\end{cases}
$$
is computable.
Let's assume that similar ...
2
There are some good books -
1. Computable Analysis - Pour-El and Richards (an older reference)
2. Computable Analysis - Weihrauch
There's also the Blum-Shub-Smale Model, which is the model explored in "Complexity and Real Computation".
The complexity theory of computability of reals is explored in
1. Computational Complexity of real functions - Ker-...
2
For $L$-Lipschitz functions on a metric space $(X,\rho)$ with $\epsilon$-packing number $M(\epsilon)$, the $\gamma$-shattering dimension is $M(2\gamma/L)$, as proved here:
http://ieeexplore.ieee.org/document/6867374/
1
I'm assuming that you're really asking, "how do I do something useful with modelling and theory."
The easiest answer is to work in a modelling and simulation field that makes useful products. Computational Electromagnetics is used a lot in RF, Finite Element Analysis is used in mechanical product design.
The broken part of your reasoning is that "more ...
1
I guess I have an alternative solution. Let $f :\subseteq \Sigma^{\omega} \to \Sigma^{\omega}$ be computable. Define
$$
h(u) = v \mbox{ iff }
f(u\Sigma^{\omega}) = \{v\} \mbox{ with $u$ minimal}
$$
and let $h(u)$ diverge otherwise. Then $\mbox{dom}(h)$ is prefix-free for if $h(u) = v$ then $f(u\Sigma^{\omega}) = \{v\}$ as the machine behaves the same when ...
1
The website of Computability and Complexity in Analysis Network has extensive bibliography. See their page for books.
For computability, see
Klaus Weihrauch, "Computable Analysis", 2010.
It also has a chpater on complexity.
See also PhD theses of Jens Blanc and Andrej Bauer.
Another interesting paper is
Viggo Stoltenberg-Hansen and John Tucker, "...
1
there may be a ref that relatively directly connects general differential equations with Turing Completeness, but am not sure what one is. wikipedia states in this section Computability theory/continuous:
Computability theory for digital computation is well developed. Computability theory is less well developed for analog computation that occurs in analog ...
Only top voted, non community-wiki answers of a minimum length are eligible
