On the Computational Complexity of Information Hiding

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 mode...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Paredes, A.R.
Formato:	JOUR
Materias:	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
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_15710661_v339_n_p135_Paredes
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_15710661_v339_n_p135_Paredes
record_format	dspace
spelling	todo:paper_15710661_v339_n_p135_Paredes2023-10-03T16:27:13Z On the Computational Complexity of Information Hiding Paredes, A.R. 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 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) JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_15710661_v339_n_p135_Paredes
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	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
spellingShingle	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 Paredes, A.R. On the Computational Complexity of Information Hiding
topic_facet	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
description	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)
format	JOUR
author	Paredes, A.R.
author_facet	Paredes, A.R.
author_sort	Paredes, A.R.
title	On the Computational Complexity of Information Hiding
title_short	On the Computational Complexity of Information Hiding
title_full	On the Computational Complexity of Information Hiding
title_fullStr	On the Computational Complexity of Information Hiding
title_full_unstemmed	On the Computational Complexity of Information Hiding
title_sort	on the computational complexity of information hiding
url	http://hdl.handle.net/20.500.12110/paper_15710661_v339_n_p135_Paredes
work_keys_str_mv	AT paredesar onthecomputationalcomplexityofinformationhiding
_version_	1782026177683128320

On the Computational Complexity of Information Hiding

Ejemplares similares