Real Analogue to CVP (RealCVP)

Input

A feasible real function $V$ defined on $(-\infty, +\infty)$.

Problem

Compute $V(x)$ with absolute error less than $2^{-n}$.

Definitions

A real function $f$ is feasible if, given a sufficiently accurate fixed-point binary approximation to $x \in [-2^n, 2^n]$, a fixed-point binary approximation to $f(x)$ with absolute error less than $2^{-n}$, can be computed in time $n^{O(1)}$. Sufficiently accurate means that the error in approximating the input $x$ is less than $2^{-n^{O(1)}}$. This fixes the number of input bits. The continuity of $f$ limits its range; thus, it fixes the number of output bits. Both are polynomial in $n$.

Status

$\P$-hard (Hoover [1][2]).

Remarks

The reduction to show hardness is from CVP. The same function yields a family of $\FP$-complete polynomials $\{p_n\}$ computable by feasible-size-magnitude. A $+$, $-$, $\times$ arithmetic circuit family is feasible-size-magnitude if the $n^\text{th}$ member is polynomial size and its output over the interval $[-2^n,+2^n]$ can be computed without generating any intermediate values with magnitude exceeding $2^{n^{O(1)}}$.