On the computational complexity of positive linear functionals on C[0;1]

Abstract

The Lebesgue integration has been related to polynomial counting complexity in several ways, even when restricted to smooth functions. We prove analogue results for the integration operator associated with the Cantor measure as well as a more general second-order #P#P-hardness criterion for such operators. We also give a simple criterion for relative polynomial time complexity and obtain a better understanding of the complexity of integration operators using the Lebesgue decomposition theorem.