Fixed Points of Contraction Mappings (FPCM)
Category: Real Analysis
Input
An $\NC$ real function $C$ that behaves as a contractor on some interval $I$ contained in $(-\infty, +\infty)$. The endpoints of $I$ are specified as integers.
Problem
Compute the fixed point of $C$ in $I$ with absolute error less than $2^{-n}$.
Definitions
A real function $f$ is in $\NC$ if an approximation to $f(x)$ with absolute error less than $2^{-n}$, for $x \in [-2^n, +2^n]$, can be computed in $\NC$ (with the same input/output conventions as for RealCVP).
Status
$\P$-hard (Hoover [1]).
Remarks
The reduction to show hardness is from CVP. This provides an argument that fast numerical methods based on fixed points probably have to use contraction maps with better than linear rates of convergence, such as Newton’s method.