Artículo
Abstract:
In this work we study the intrinsic complexity of elimination algorithms in effective algebraic geometry and we focus our attention to elimination algorithms produced within the object–oriented paradigm. To this end, we describe a new computation model called quiz game (introduced in [1]) which models the notions of information hiding (due to Parnas, see [8]) and non–functional requirements (e.g. robustness) among other important concepts in software engineering. This characteristic distinguish our model from classical computation models such as the Turing machine or algebraic models. We illustrate our computation model with a non–trivial complexity lower bound for the identity function of polynomials. We show that any object–oriented (and robust) implementation of the identity function of polynomials is necessarily inefficient compared with a trivial implementation of this function. This result shows an existing synergy between Software Engineering and Algebraic Complexity Theory. Keywords: Abstract data type, abstraction function, data structure, information hiding, lower complexity bound, non–functional requirement, quantifier elimination, quiz game, robustness, scientific computing. © 2018 The Author(s)
Registro:
| Documento: | Artículo |
| Título: | On the Computational Complexity of Information Hiding |
| Autor: | Paredes, A.R. |
| Filiación: | Instituto de Ciencias, Universidad Nacional de General Sarmiento, J. M. Gutiérrez 1150 (B1613GSX), Los Polvorines, Provincia de Buenos Aires, Argentina Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I (C1428EGA), Ciudad Universitaria, CABA, Argentina |
| Palabras clave: | Abstract data types; Algebra; Computer games; Software engineering; Turing machines; Abstraction functions; Algebraic complexity theories; Algebraic geometry; Computation model; Functional requirement; Identity functions; Information hiding; Quantifier elimination; Computational complexity |
| Año: | 2018 |
| Volumen: | 339 |
| Página de inicio: | 135 |
| Página de fin: | 146 |
| DOI: | http://dx.doi.org/10.1016/j.entcs.2018.06.009 |
| Título revista: | Electronic Notes in Theoretical Computer Science |
| Título revista abreviado: | Electron. Notes Theor. Comput. Sci. |
| ISSN: | 15710661 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710661_v339_n_p135_Paredes |
Referencias:
- Bank, B., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M., Rojas, A., Paredes, Quiz Games as a Model for Information Hiding (2016) Journal of Complexity, 34, pp. 1-29
- Giménez, N., Heintz, J., Matera, G., Solernó, P., Lower Complexity Bounds for Interpolation Algorithms (2011) Journal of Complexity, 27, pp. 151-187
- Giusti, M., Lecerf, G., Salvy, B., A Gröbner Free Alternative for Polynomial System Solving (2001) Journal of Complexity, 17, pp. 154-211. , http://www.sciencedirect.com/science/article/pii/S0885064X00905715
- Heintz, J., Kuijpers, B., Rojas, A., Paredes, Software Engineering and Complexity in Effective Algebraic Geometry (2013) Journal of Complexity, 29, pp. 92-138
- Heintz, J., Morgenstern, J., On the Intrinsic Complexity of Elimination Theory (1993) Journal of Complexity, 9, pp. 471-498
- Kollar, J., Effective Nullstellensatz, S., (1988) Journal of the American Mathematical Society, 1, pp. 963-975
- Meyer, B., Object–Oriented Software Construction (1997), 2 edition Prentice-Hall, Inc. Upper Saddle River, NJ, USA; Parnas, D.L., On the Criteria to Be Used in Decomposing Systems into Modules (1972) Commun. ACM, 15, pp. 1053-1058
- Puddu, S.I., Un Algoritmo Efectivo para la Eliminación de Cuantificadores (1995), Ph.D. thesis Universidad de Buenos Aires Argentina; Rojas Paredes, A., Complexity as Quality Attribute in Software Design (2011), Master's thesis Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires Pabellón 1, Ciudad Universitaria; Sombra, M., A Sparse Effective Nullstellensatz (1999) Adv. Appl. Math., 22, pp. 271-295. , https://doi.org/10.1006/aama.1998.0633
Citas:
---------- APA ----------
(2018) . On the Computational Complexity of Information Hiding. Electronic Notes in Theoretical Computer Science, 339, 135-146.http://dx.doi.org/10.1016/j.entcs.2018.06.009
---------- CHICAGO ----------
Paredes, A.R. "On the Computational Complexity of Information Hiding" . Electronic Notes in Theoretical Computer Science 339 (2018) : 135-146.http://dx.doi.org/10.1016/j.entcs.2018.06.009
---------- MLA ----------
Paredes, A.R. "On the Computational Complexity of Information Hiding" . Electronic Notes in Theoretical Computer Science, vol. 339, 2018, pp. 135-146.http://dx.doi.org/10.1016/j.entcs.2018.06.009
---------- VANCOUVER ----------
Paredes, A.R. On the Computational Complexity of Information Hiding. Electron. Notes Theor. Comput. Sci. 2018;339:135-146.http://dx.doi.org/10.1016/j.entcs.2018.06.009
