We develop a complexity theory for approximate real computations. We first produce a theory for exact computations but with condition numbers. The input size depends on a condition number, which is not assumed known by the machine. The theory admits deterministic and nondeterministic polynomial time recognizable problems. We prove that P is not NP in this theory if and only if P is not NP in the BSS theory over the reals. Then we develop a theory with weak and strong approximate computations. This theory is intended to model actual numerical computations that are usually performed in floating point arithmetic. It admits classes P and NP and also an NP-complete problem. We relate the P vs. NP question in this new theory to the classical P vs. NP problem.

A model for computation over an arbitrary (ordered) ring R is presented. In this general setting, universal machines, partial recursive functions, and NP-complete problems are obtained. While the theory reflects of classical over Z (e.g. the computable functions are the recursive functions), it also reflects the special mathematical character of the underlying ring R (e.g. complements of Julia sets provide natural examples of recursively enumerable undecidable sets over the reals) and provides a natural setting for studying foundational issues concerning algorithms in numerical analysis.>

Two closely-related pseudo-random sequence generators are presented: The ${1 / P}$generator, with input P a prime, outputs the quotient digits obtained on dividing 1 by P. The $x^2 \bmod N$generator with inputs N, $x_0 $ (where $N = P \cdot Q$ is a product of distinct primes, each congruent to 3 mod 4, and $x_0 $ is a quadratic residue $\bmod N$), outputs $b_0 b_1 b_2 \cdots $ where $b_i = {\operatorname{parity}}(x_i )$ and $x_{i + 1} = x_i^2 \bmod N$. From short seeds each generator efficiently produces long well-distributed sequences. Moreover, both generators have computationally hard problems at their core. The first generator’s sequences, however, are completely predictable (from any small segment of $2|P| + 1$ consecutive digits one can infer the “seed,” P, and continue the sequence backwards and forwards), whereas the second, under a certain intractability assumption, is unpredictable in a precise sense. The second generator has additional interesting properties: from knowledge of $x_0 $ and N but notP or Q, one can generate the sequence forwards, but, under the above-mentioned intractability assumption, one can not generate the sequence backwards. From the additional knowledge of P and Q, one can generate the sequence backwards; one can even “jump” about from any point in the sequence to any other. Because of these properties, the $x^2 \bmod N$generator promises many interesting applications, e.g., to public-key cryptography. To use these generators in practice, an analysis is needed of various properties of these sequences such as their periods. This analysis is begun here.

If one is interested in the computational complexity of problems whose natural domain of discourse is the reals, then one is led to ask: what is the “cost” of obtaining solutions to within a prescribed absolute accuracy$\varepsilon = {1 / {2^s }}$ (or precision$s = - \log _2 \varepsilon $)? The loss of precision intrinsic to solving a problem, independent of method of solution, gives a lower bound on the cost. It also indicates how realistic it is to assume that basic (arithmetic) operations are exact and/or take one step for complexity analyses. For the relative case, the analogous notion is the loss of significance. Let ${{P(X)} / {Q(X)}}$ be a rational function of degree d, dimension n and real coefficients of absolute value bounded by $\rho $. The loss of precision in evaluating ${P / Q}$ will depend on the input x, and, in general, can be arbitrarily large. We show that, w.r.t. normalized Lebesgue measure on $B_r $, the ball of radius r about the origin in $R^n $, the average loss is small: loglinear in d, n, $\rho $, r; and $K_Q $, a simple constant. To get this, we use techniques of integral geometry and geometric measure theory to estimate the volume of the set of points causing the denominator values to be small. Suppose $\varepsilon > 0$ and $d \geqq 1$. Then: Theorem. Normalized volume$\{ x \in B_r | {|Q(x)| < \varepsilon } \} < \varepsilon ^{{1 / d}} K_Q^{{1 / d}} {{nd(d + 1)} / {2r}}$. An immediate application is a loglinear upper bound on the average loss of significance for solving systems of linear equations.

This paper deals with traditional algorithms, Newton’s method and a higher order generalization due to Euler. These iterations schemes and their modifications have had a great success in solving nonlinear systems of equations. We give some understanding of this phenomenon by giving estimates of efficiency. The problem we focus on is that of finding a zero of a complex polynomial.

We consider the following generalization of the familiar '15-puzzle' which arises from issues in memory manngrment in distributed systems: Iet G be a graph with n vertices with k3) upper and lower bounds on the number of moves required. We have the following subexponential bound for certain unbounded cycles, one of which has prime length p ⩽ 2n/3, and G is primitive, then G = Anor Snand has diameter ⩽ 26 [(√(p+4))n8.