×

The computational complexity of maximization and integration. (English) Zbl 0563.03023

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.
Reviewer: S.P.Yukna

MSC:

03D15 Complexity of computation (including implicit computational complexity)
26A21 Classification of real functions; Baire classification of sets and functions
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI

References:

[1] Ko, K.; Friedman, H., Computational complexity of real functions, J. Theoret. Comp. Sci., 20, 323-352 (1982) · Zbl 0498.03047
[2] Ko, K., The maximum value problem and NP real numbers, J. Comput. System Sci., 24, 15-35 (1982) · Zbl 0481.03038
[3] Valiant, L., The complexity of enumeration and reliability problems, SIAM J. Comput., 8, No. 3, 410-421 (1979) · Zbl 0419.68082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.