Ian Munro
ABSTRACT
Computational Complexity is concerned with how difficult, under some measure of difficulty, it is to evaluate certain functions or classes of functions. Most of the work in this area, however, deals with models of computation quite unlike a stored program computer, and functions very different from those which are actually computed. In this paper we turn our attention to techniques of computing some useful functions on “computer-like” devices in optimal or near optimal ways.
- 1.Pan, V. Ya, "Methods of Computing Values of Polynomials", Russian Mathematical Surveys, Vol. 21, No. 1, pp 105-6.Google Scholar
- 2.Borodin, A., "Some Results on the Computation of Polynomial Forms", unpublished manuscript.Google Scholar
- 3.Winograd, S., "On the Number of Multiplications Required to Compute Certain Functions", Proc. National Academy of Sciences 58:5, pp 1840-2 and IBM Internal Report.Google ScholarCross Ref
- 4.Hopcroft, J., Personal Communication.Google Scholar
- 5.Paterson, M., Personal Communication.Google Scholar
- 6.Brauer, A., Bull. AMS 45(1939), pp 736-9.Google ScholarCross Ref
- 7.Erdös, Paul, Acta Arithmetica 6(1960), pp 77-81.Google Scholar
- 8.Knuth, D., The Art of Computer Programming, Vol. 2. Google ScholarDigital Library
Index Terms
- Some results concerning efficient and optimal algorithms
Recommendations
Some new results concerning the Smarandache Ceil function
In this article we present two new results concerning the Smarandache Ceil function. The first result proposes an equation for the number of fixed-point number of the Smarandache ceil function. Based on this result we prove that the average of the ...
Some new results concerning the Smarandache Ceil function
Smarandache notionsIn this article we present two new results concerning the Smarandache Ceil function. The first result proposes an equation for the number of fixed-point number of the Smarandache ceil function. Based on this result we prove that the average of the ...
On some questions concerning strong compactness
AbstractA question of Woodin asks if κ is strongly compact and GCH holds below κ, then must GCH hold everywhere? One variant of this question asks if κ is strongly compact and GCH fails at every regular cardinal δ < κ, then must GCH fail at some regular ...
Comments