On the Complexity of Real Functions

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object 15 Nov 2005Embargo end date: 01 Jan 2005Publisher:IEEEJournal:46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)Funded by:NSERC | unidentified

Authors: Mark Braverman;

doi: 10.1109/sfcs.2005.58 , 10.48550/arxiv.cs/0502066

arXiv: cs/0502066

On the Complexity of Real Functions

- Summary
- Subjects
- Metrics

Abstract

We develop a notion of computability and complexity of functions over the reals, which seems to be very natural when one tries to determine just how "difficult" a certain function is. This notion can be viewed as an extension of both BSS computability [Blum, Cucker, Shub, Smale 1998], and bit computability in the tradition of computable analysis [Weihrauch 2000] as it relies on the latter but allows some discontinuities and multiple values.

Related Organizations

University of Toronto
Canada

Keywords

FOS: Computer and information sciences, Computer Science - Computational Complexity, F. 1.1; F. 4. 1, F. 1.1, FOS: Mathematics, Mathematics - Numerical Analysis, F. 4. 1, Numerical Analysis (math.NA), Computational Complexity (cs.CC)

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	21
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%