On the Complexity of Familiar Functions and Numbers

Publisher Website
Google Scholar
Abstract
This paper examines low-complexity approximations to familiar functions and numbers. The intent is to suggest that it is possible to base a taxonomy of such functions and numbers on their computational complexity. A central theme is that traditional methods of approximation are often very far from optimal, while good or optimal methods are often very far from obvious. For most functions, provably optimal methods are not known; however the gap between what is known and what is possible is often small. A considerable number of open problems are posed and a number of related examples are presented.

This publication has 11 references indexed in Scilit: