Busque entre los 156185 recursos disponibles en el repositorio
Mostrar el registro sencillo del ítem
dc.date.accessioned | 2013-12-17T17:07:54Z | |
dc.date.available | 2013-12-17T17:07:54Z | |
dc.date.issued | 2013-10 | |
dc.identifier.uri | http://sedici.unlp.edu.ar/handle/10915/32381 | |
dc.description.abstract | We consider the problem of polynomial equation solving also known as quantifier elimination in Effective Algebraic Geometry. The complexity of the first elimination algorithms were double exponential, but a considerable progress was carried out when the polynomials were represented by arithmetic circuits evaluating them. This representation improves the complexity to pseudo–polynomial time. The question is whether the actual asymptotic complexity of circuit– based elimination algorithms may be improved. The answer is no when elimination algorithms are constructed according to well known software engineering rules, namely applying information hiding and taking into account non–functional requirements. These assumptions allows to prove a complexity lower bound which constitutes a mathematically certified non–functional requirement trade–off and a surprising connection between Software Engineering and the theoretical fields of Algebraic Geometry and Computational Complexity Theory. | es |
dc.language | es | es |
dc.subject | non-functional requirement trade–off | es |
dc.subject | information hiding | es |
dc.subject | arithmetic circuit | es |
dc.subject | complexity lower bound | es |
dc.subject | polynomial equation solving | es |
dc.subject | quantifier climination in algebraic geometry | es |
dc.title | A complexity lower bound based on software engineering concepts | es |
dc.type | Objeto de conferencia | es |
sedici.creator.person | Rojas Paredes, Andrés | es |
sedici.description.note | WATCC - IV Workshop aspectos teóricos de ciencia de la computación | es |
sedici.subject.materias | Ciencias Informáticas | es |
sedici.description.fulltext | true | es |
mods.originInfo.place | Red de Universidades con Carreras en Informática (RedUNCI) | es |
sedici.subtype | Objeto de conferencia | es |
sedici.rights.license | Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Argentina (CC BY-NC-SA 2.5) | |
sedici.rights.uri | http://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | |
sedici.relation.event | XVIII Congreso Argentino de Ciencias de la Computación | es |
sedici.description.peerReview | peer-review | es |