On the Computational Complexity of Best L1-approximation
Paulo B. Oliva · Mathematical logic quarterly · 2002
It is well known that for a given continuous function f : [0, 1] → ℝ and a number n there exists a unique polynomial pn ∈ Pn (polynomials of degree ≤ n) which best L1-approximates f. We establish the first upper bound on the complexity of the sequence (pn)n∈ ℕ, assuming f is polynomial-time computable. Our complexity analysis makes essential use of the modulus of uniqueness for L1-approximation presented in [13].