OMEGA-((N-LG N)1/2) LOWER BOUND ON THE NUMBER OF ADDITIONS NECESSARY TO COMPUTE 0-1 POLYNOMIALS OVER THE RING OF INTEGER POLYNOMIALS

被引：0
作者：
RIVEST, RL
VANDEWIELE, JP
机构：
[1] Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
来源：
INFORMATION PROCESSING LETTERS | 1979年 / 8卷 / 04期
关键词：
0-1; polynomials; additive complexity; Computational complexity; integer preconditioning; lower bound; polynomial evaluation;
D O I：
10.1016/0020-0190(79)90018-8
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
[No abstract available]
引用
收藏
页码：178 / 180
页数：3
相关论文
共 4 条
  • [1] Paterson, Stockmeyer, On the number of non scalar multiplications necessary to evaluate polynomials, SIAM Journal on Computing, 2, 1, pp. 60-66, (1973)
  • [2] Savage, An algorithm for the computation of linear firms, SIAM Journal on Computing, 3, 2, pp. 150-158, (1974)
  • [3] Trost, Primzahlen, (1953)
  • [4] van de Wiele, An optimal lower bound on the number of total operations to compute 0–1 polynomials over the field of complex numbers, Rapport Laboria No. 303, (1978)
1