The computational complexity of maximization and integration

DOI10.1016/0001-8708(84)90019-7zbMath0563.03023OpenAlexW2067459389MaRDI QIDQ1057267

Harvey M. Friedman

Publication date: 1984

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0001-8708(84)90019-7

zbMATH Keywords

computational complexitypolynomial timereal function

Mathematics Subject Classification ID

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

Related Items (22)

Continuous optimization problems and a polynomial hierarchy of real functions ⋮ Approximation to measurable functions and its relation to probabilistic computation ⋮ Some observations on the connection between counting and recursion ⋮ Computing power series in polynomial time ⋮ On parallel complexity of analytic functions ⋮ On the computational complexity of the Dirichlet Problem for Poisson's Equation ⋮ Unnamed Item ⋮ Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy ⋮ A polynomial-time computable curve whose interior has a nonrecursive measure ⋮ Some aspects of effectively constructive mathematics that are relevant to the foundations of neoclassical mathematical economics and the theory of games ⋮ Complexity of Operators on Compact Sets ⋮ On the Complexity of Convex Hulls of Subsets of the Two-Dimensional Plane ⋮ On the computational complexity of integral equations ⋮ Analytical properties of resource-bounded real functionals ⋮ Parametrised second-order complexity theory with applications to the study of interval computation ⋮ On subrecursive complexity of integration ⋮ On the computational complexity of best Chebyshev approximations ⋮ Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics ⋮ On some natural complete operators ⋮ Computable Measure Theory and Algorithmic Randomness ⋮ Real functions, contraction mappings, and P-completeness ⋮ Effectively closed sets and graphs of computable real functions.

Cites Work

• The maximum value problem and NP real numbers
• Computational complexity of real functions
• The Complexity of Enumeration and Reliability Problems

This page was built for publication: The computational complexity of maximization and integration