TY - JOUR

T1 - Complexity measures and hierarchies for the evaluation of integers and polynomials

AU - Lipton, Richard J.

AU - Dobkin, David

N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

PY - 1976/12

Y1 - 1976/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=36348952198&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=36348952198&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(76)90051-7

DO - 10.1016/0304-3975(76)90051-7

M3 - Article

AN - SCOPUS:36348952198

VL - 3

SP - 349

EP - 357

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 3

ER -