On the representation of rational functions of bounded complexity. (English) Zbl 0679.68099
Summary: The main result of this article is the Representation Theorem which characterizes families of rational functions of bounded complexity by appropriate mappings. This description is not only independent of the characteristic of the underlying field but also of the specific complexity measure under consideration. As an application of the Representation Theorem we derive good lower complexity bounds.
References:
| [1] | Borodin, A.; Cook, S., On the number of additions to compute specific polynomials, SIAM J. Comp., 5, 146-157 (1976) · Zbl 0341.65034 |
| [2] | Borodin, A.; Munro, I., The Computational Complexity of Algebraic and Numeric Problems (1975), Elsevier: Elsevier New York · Zbl 0404.68049 |
| [3] | Von zur Gathen, J.; Strassen, V., Some polynomials that are hard to compute, Theoret. Comput. Sci., 11, 331-335 (1980) · Zbl 0442.68028 |
| [4] | J. Heintz, Private communication (1984).; J. Heintz, Private communication (1984). |
| [5] | Heintz, J.; Schnorr, C. P., Testing polynomials which are easy to compute, Proc. 12th Ann. ACM Symp. on Computing, 262-280 (1980) |
| [6] | Heintz, J.; Sieveking, M., A new method to show lower bounds for polynomials which are hard to compute, Theoret. Comput. Sci., 11, 321-330 (1980) · Zbl 0452.68051 |
| [7] | Paterson, M. S.; Stockmeyer, L. J., On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM J. Comp., 2, 60-66 (1973) · Zbl 0262.65033 |
| [8] | Schnorr, C. P., Improved lower bounds on the number of multiplications⧸divisions which are necessary to evaluate polynomials, Theoret. Comput. Sci., 7, 251-261 (1978) · Zbl 0387.68034 |
| [9] | Schnorr, C. P.; van de Wiele, J. P., On the additive complexity of polynomials, Theoret. Comput. Sci., 10, 1-18 (1980) · Zbl 0469.68044 |
| [10] | Stoß, H.-J., Lower bounds on the complexity of polynomials, Theoret. Comput. Sci., 64, 15-23 (1989), (this issue) · Zbl 0679.68098 |
| [11] | Strassen, V., Berechnung und Programm I, Acta Inform., 1, 320-334 (1972) · Zbl 0252.68018 |
| [12] | Strassen, V., Polynomials with rational coefficients which are hard to compute, SIAM J. Comp., 3, 129-149 (1974) · Zbl 0289.68018 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
