Geodesic
A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF
Forum of Mathematics, Sigma, Tome 3 (2015)

Voir la notice de l'article provenant de la source Cambridge University Press

We develop a theory of complexity for numerical computations that takes into account the condition of the input data and allows for roundoff in the computations. We follow the lines of the theory developed by Blum, Shub and Smale for computations over $\mathbb{R}$ (which in turn followed those of the classical, discrete, complexity theory as laid down by Cook, Karp, and Levin, among others). In particular, we focus on complexity classes of decision problems and, paramount among them, on appropriate versions of the classes $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{EXP}$ of polynomial, nondeterministic polynomial, and exponential time, respectively. We prove some basic relationships between these complexity classes, and provide natural NP-complete problems. 
@article{10_1017_fms_2015_2,
     author = {FELIPE CUCKER},
     title = {A {THEORY} {OF} {COMPLEXITY,} {CONDITION,} {AND} {ROUNDOFF}},
     journal = {Forum of Mathematics, Sigma},
     publisher = {mathdoc},
     volume = {3},
     year = {2015},
     doi = {10.1017/fms.2015.2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2015.2/}
}
TY  - JOUR
AU  - FELIPE CUCKER
TI  - A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF
JO  - Forum of Mathematics, Sigma
PY  - 2015
VL  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2015.2/
DO  - 10.1017/fms.2015.2
LA  - en
ID  - 10_1017_fms_2015_2
ER  - 
%0 Journal Article
%A FELIPE CUCKER
%T A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF
%J Forum of Mathematics, Sigma
%D 2015
%V 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2015.2/
%R 10.1017/fms.2015.2
%G en
%F 10_1017_fms_2015_2
FELIPE CUCKER. A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF. Forum of Mathematics, Sigma, Tome 3 (2015). doi: 10.1017/fms.2015.2

Cité par Sources :