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