Complexity measures and hierarchies for the evaluation of integers and polynomials

Richard J. Lipton, David Dobkin

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


The complexity of evaluating integers and polynomials is studied. A new model is proposed for studying such complexities. This model differs from previous models by requiring the construction of constant to be used in the computation. This construction is given a cost which is dependent upon the size of the constant. Previous models used a uniform cost, of either 0 or 1, for operations involving constants. Using this model, proper hierarchies are shown to exist for both integers and polynomials with respect to evaluation cost. Furthmore, it is shown that almost all integers (polynomials) are as difficult to evaluate as the hardest integer (polynomial). These results remain true even if the underlying basis of binary operations which the algorithm performs are varied.

Original languageEnglish (US)
Pages (from-to)349-357
Number of pages9
JournalTheoretical Computer Science
Issue number3
StatePublished - Dec 1976

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Complexity measures and hierarchies for the evaluation of integers and polynomials'. Together they form a unique fingerprint.

Cite this