The computational complexity of maximization and integration (Q1057267)

A number of computational complexity questions concerning basic real analysis are considered such as the following. Is the maximum \(\max_{y\in [0,1]}g(x,y)\) of every polynomial time computable (PTC for short) real function g, a PTC real function? Is the definite integral \(\int^{1}_{0}g(x,y)dx\) of every PTC real function g, a PTC real function? The author shows that the first question has an affirmative answer iff \(P=NP\) and the second question has an affirmative answer iff {\#}P\(=P\), i.e., iff for every PTC predicate R(x,y) on \(\{0,1\}^*\) and a polynomial q, the function h given by h(x) is the base 2 representation of card\(\{\) \(y: | y| \leq q(| x|)\) and R(x,y)\(\}\), is polynomial time computable.