Title :
Computational complexity of roots of real functions
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Stony Brook, NY, USA
fDate :
30 Oct-1 Nov 1989
Abstract :
An attempt is made to give a more accurate classification of the computational complexity of roots of real functions. Attention is focused on the simplest types of functions, namely, one-to-one and k -to-one functions, and the complexity of their roots is characterized in terms of relations between discrete complexity classes, such as LOGSPACE, P, UP, and NP
Keywords :
computational complexity; LOGSPACE; NP; P; UP; classification; computational complexity; discrete complexity classes; k-to-one functions; one-to-one; roots of real functions; Algorithm design and analysis; Complexity theory; Computational complexity; Computational modeling; Computer science; Polynomials;
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
DOI :
10.1109/SFCS.1989.63479
