VPSPACE and a transfer theorem over the complex field

Autor: Pascal Koiran, Sylvain Perifel

Publikováno v: MFCS

We extend the transfer theorem of [14] to the complex field. That is, we investigate the links between the class VPSPACE of families of polynomials and the Blum–Shub–Smale model of computation over C. Roughly speaking, a family of polynomials is

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1146cd9898410924e2645f7a083fe9fa
https://doi.org/10.1016/j.tcs.2009.08.026

VPSPACE and a transfer theorem over the complex field

Autor: Koiran, Pascal, Perifel, Sylvain

We extend the transfer theorem of [KP2007] to the complex field. That is, we investigate the links between the class VPSPACE of families of polynomials and the Blum-Shub-Smale model of computation over C. Roughly speaking, a family of polynomials is

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fe6f160707ffcf68094f76afbaba2d1d
https://ens-lyon.hal.science/ensl-00153701/document

On the Complexity of Numerical Analysis

Autor: Eric Allender, Johan Kjeldgaard-Pedersen, Peter Bürgisser, Peter Bro Miltersen

Publikováno v: Miltersen, P B, Kjeldgaard-Pedersen, J, Burgisser, P & Allender, E 2006, On the Complexity of Numerical Analysis . in Proceedings of the 21st Annual IEEE Conference on Computational Complexity . IEEE Computer Society Press, pp. 331-339, IEEE Conference on Computational Complexity, Prague, Czech Republic, 17/12/2010 .
IEEE Conference on Computational Complexity
Allender, E, Bürgisser, P, Kjeldgaard-Pedersen, J & Miltersen, P B 2005, ' On the Complexity of Numerical Analysis ', Electronic Colloquium on Computational Complexity, no. TR05-037, pp. 1-12 .
Miltersen, P B, Allender, E, Burgisser, P & Kjeldgaard-Pedersen, J 2009, ' On the complexity of numerical analysis ', S I A M Journal on Computing, vol. 38, no. 5, pp. 1987-2006 . https://doi.org/10.1137/070697926

Udgivelsesdato: January 14 We study two quite different approaches to understanding the complexity of fundamental problems in numerical analysis: • The Blum-Shub-Smale model of computation over the reals. • A problem we call the “Generic Task o

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::878d8dbc8d69381d026cb3f23d41109e
https://pure.au.dk/portal/da/publications/on-the-complexity-of-numerical-analysis(e41267f0-255d-11dc-bee9-02004c4f4f50).html

An Embedding of the BSS Model of Computation in Light Affine Lambda-Calculus

Autor: Baillot, Patrick, Pedicini, Marco

Publikováno v: 8th International Workshop on Logic and Computational Complexity Seattle, August 10-11, 2006 (Satellite Workshop of FLOC-LICS 2006)
8th International Workshop on Logic and Computational Complexity Seattle, August 10-11, 2006 (Satellite Workshop of FLOC-LICS 2006), 2006, Seattle, United States

This paper brings together two lines of research: implicit characterization of complexity classes by Linear Logic (LL) on the one hand, and computation over an arbitrary ring in the Blum-Shub-Smale (BSS) model on the other. Given a fixed ring structu

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e2e0e25a488e75513bb4b51ef864a998
https://hal.archives-ouvertes.fr/hal-00085547

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.