Abstract
Based on the results of Blum, Shub and Smale [1], Meer [6], Cucker and Matamala [3] and Koiran [4], we develop the study of real computation models restricted to additive operations. More specifically we introduce some complexity classes defined by algebraic circuits and we study their relationships with the real computation model. We show that the languages accepted by nonuniform additive circuits of polynomial size and polylogarithmic depth are those accepted by uniform additive circuits of polynomial size and polylogarithmic depth with advice. Moreover, we prove that binary languages accepted by real uniform circuits of polynomial size and polylogarithmic depth, when the test nodes in the circuit are equality test, are the languages belonging to NC; when the test nodes are inequality test, the class obtained is NC/Poly. We also prove that the class defined by family of algebraic circuits with polynomial size and polylogarithmic depth is strictly contained in the class defined by real additive Turing machines working in polynomial time.
Supported by the Programme de Recherche Coordonnée PRS, The ESPRIT Working Group NeuroCOLT and by Grant Marie Curie ERBCISTGT 920031
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Blum and M. Shub and S. Smale: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the Amer. Math. Soc. 21 (1989) 1–46
F. Cucker: PR⪿ NC R. J. of Complexity (1992) 230–238
F. Cucker and M. Matamala: On Weak nondeterminism. Preprint (1993)
F. Cucker and P. Koiran: Computing over the reals with addition and order: higher complexity classes. Preprint DIMACS.
P. Koiran: A weak version of the Blum, Shub and Smale model. 1993 IEEE Symposium on Foundations Of Computer Science 486–495 (1993)
K. Meer: A note on a P≠ NP result for a restricted class of real machines. J. of Complexity (1992) 451–453
C. Michaux: Une remarque à propos des machines sur R introduites par Blum, Shub et Smale. C.R. Acad. Sci. Paris série I, France 309 (1989) 435–437
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cosnard, M., Matamala, M. (1994). On NC-real complexity classes for additive circuits and their relations with NC. In: Prívara, I., Rovan, B., Ruzička, P. (eds) Mathematical Foundations of Computer Science 1994. MFCS 1994. Lecture Notes in Computer Science, vol 841. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58338-6_56
Download citation
DOI: https://doi.org/10.1007/3-540-58338-6_56
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58338-7
Online ISBN: 978-3-540-48663-3
eBook Packages: Springer Book Archive