Approximation error: Difference between revisions

Revision as of 22:10, 29 December 2024

Revision as of 05:32, 25 April 2025

Line 43:

We say that a real value ''v'' is '''polynomially computable with absolute error''' from an input if, for every rational number ''ε''>0, it is possible to compute a rational number ''v''_approx that approximates ''v'' with absolute error ''ε'', in time polynomial in the size of the input and the encoding size of ''ε'' (which is O(log(1/''ε'')). Analogously, ''v'' is '''polynomially computable with relative error''' if, for every rational number ''η''>0, it is possible to compute a rational number ''v''_approx that approximates ''v'' with relative error ''η'', in time polynomial in the size of the input and the encoding size of ''η''.

If ''v'' is polynomially computable with relative error (by some algorithm called REL), then it is also polynomially computable with absolute error. ''Proof''. Let ''ε''>0 be the desired absolute error. First, use REL with relative error ''η=''=1/2; find a rational number ''r''₁ such that |''v''-&minus;''r''₁| ≤ |''v''|/2, and hence |''|v|''| ≤ 2 |''r''₁|. If ''r''₁=0, then ''v''=0 and we are done. Since REL is polynomial, the encoding length of ''r''₁ is polynomial in the input. Now, run REL again with relative error ''η''=''ε/''/(2 |''|r''₁|). This yields a rational number ''r''₂ that satisfies |''v''-&minus;''r''₂| ≤ ''ε''|''v''| / (2''r''₁) ≤ ''ε'', so it has absolute error ''ε'' as wished.<ref name=":02" />{{Rp|page=34}}

The reverse implication is usually not true. But, if we assume that some positive lower bound on |''v''| can be computed in polynomial time, e.g. |''v''| > ''b'' > 0, and ''v'' is polynomially computable with absolute error (by some algorithm called ABS), then it is also polynomially computable with relative error, since we can simply call ABS with absolute error ''ε'' = ''η b.''.

An algorithm that, for every rational number ''η''>0, computes a rational number ''v''_approx that approximates ''v'' with relative error ''η'', in time polynomial in the size of the input and 1/''η'' (rather than log(1/''η'')), is called an [[FPTAS]].

==Instruments==