Information-Based Complexity
J. F. Traub, H. Wozniakowski · Science · 1989
Computational complexity studies the intrinsic difficulty of mathematically posed problems and seeks optimal means for their solutions. This is a rich and diverse field; for the purpose of this paper we present a greatly simplified picture. Computational complexity may be divided into two branches, discrete and continuous.
Cited by 843 works. doi:10.1126/science.243.4895.1142-a
References
- A Fast Monte-Carlo Test for Primality
- Sequential minimax search for a maximum
- Iterative Methods for the Solution of Equations.
- A Survey of Optimal Recovery
- On irregularities of distribution
- A new fault-tolerant algorithm for clock synchronization
- A General Theory of Optimal Algorithms
- Gaussian measures in Banach spaces
- An upper and lower bound for clock synchronization
- Best Approximate Integration Formulas; Best Approximation Formulas