Loading...
Loading...

Go to the content (press return)

Some comments about notations of orders of magnitude

Author
Balcazar, J. L.; Gabarro, J.
Type of activity
Journal article
Journal
Bulletin of the European Association for Theoretical Computer Science
Date of publication
1986-04
Volume
1
Number
30
First page
34
Last page
42
Abstract
The properties of classes defined by lower bounds on certain measures are considered, along with the `duality' relationship between lower and upper bounds. The need of a formalization of some clear, intuitive facts was apparent and, when worked out, it turned out to require more thought than the authors expected. They found themselves again and again stating `obvious' facts about orders of magnitude which when formalized were false, or at least not completely correct. They present the formalizat...
Keywords
Computational complexity, Duality, Lower bounds, Notations, Orders of magnitude, Upper bounds
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods
LARCA - Laboratory of Relational Algorithmics, Complexity and Learnability

Participants