  A famous result due to Ko and Friedman (1982) asserts that the problems of
integration and maximisation of a univariate real function are computationally
hard in a well-defined sense. Yet, both functionals are routinely computed at
great speed in practice. We aim to resolve this apparent paradox by studying
classes of functions which can be feasibly integrated and maximised, together
with representations for these classes of functions which encode the
information which is necessary to uniformly compute integral and maximum in
polynomial time. The theoretical framework for this is the second-order
complexity theory for operators in analysis which was introduced by Kawamura
and Cook (2012). The representations we study are based on rigorous
approximation by polynomials, piecewise polynomials, and rational functions. We
compare these representations with respect to polytime reducibility as well as
with respect to their ability to quickly evaluate symbolic expressions in a
given language. We show that the representation based on rigorous approximation
by piecewise polynomials is polytime equivalent to the representation based on
rigorous approximation by rational functions. With this representation, all
terms in a certain language, which is expressive enough to contain the maximum
and integral of most functions of practical interest, can be evaluated in
polynomial time. By contrast, both the representation based on polynomial
approximation and the standard representation based on function evaluation,
which implicitly underlies the Ko-Friedman result, require exponential time to
evaluate certain terms in this language. We confirm our theoretical results by
an implementation in Haskell, which provides some evidence that second-order
polynomial time computability is similarly closely tied with practical
feasibility as its first-order counterpart.
