Computational complexity of roots of real functions

Author

Ko, Ker-I

Author_Institution

Dept. of Comput. Sci., State Univ. of New York, Stony Brook, NY, USA

fYear

1989

fDate

30 Oct-1 Nov 1989

Firstpage

204

Lastpage

209

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Foundations of Computer Science, 1989., 30th Annual Symposium on

Conference_Location

Research Triangle Park, NC

Print_ISBN

0-8186-1982-1

Type

conf

DOI

10.1109/SFCS.1989.63479

Filename

63479

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2125387