Title :
Polynomials with 0-1 coefficients that are hard to evaluate
Author :
Lipton, Richard J.
Abstract :
We show the existence of polynomials with 0-1 coefficients that are hard to evaluate even when arbitrary preconditioning is allowed. Further we show that there are power series with 0-1 coefficients such that their initial segments are hard to evaluate.
Keywords :
Computational modeling; Computer science; Costs; Polynomials;
Conference_Titel :
Foundations of Computer Science, 1975., 16th Annual Symposium on
Conference_Location :
USA
DOI :
10.1109/SFCS.1975.25
