A complexity lower bound based on software engineering concepts

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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Rojas Paredes, Andrés
Formato: Objeto de conferencia
Lenguaje:Español
Publicado: 2013
Materias:
Ciencias Informáticas
non-functional requirement trade–off
information hiding
arithmetic circuit
complexity lower bound
polynomial equation solving
quantifier climination in algebraic geometry
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/32381
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-32381
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
non-functional requirement trade–off
information hiding
arithmetic circuit
complexity lower bound
polynomial equation solving
quantifier climination in algebraic geometry
spellingShingle Ciencias Informáticas
non-functional requirement trade–off
information hiding
arithmetic circuit
complexity lower bound
polynomial equation solving
quantifier climination in algebraic geometry
Rojas Paredes, Andrés
A complexity lower bound based on software engineering concepts
topic_facet Ciencias Informáticas
non-functional requirement trade–off
information hiding
arithmetic circuit
complexity lower bound
polynomial equation solving
quantifier climination in algebraic geometry
description 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.
format Objeto de conferencia
Objeto de conferencia
author Rojas Paredes, Andrés
author_facet Rojas Paredes, Andrés
author_sort Rojas Paredes, Andrés
title A complexity lower bound based on software engineering concepts
title_short A complexity lower bound based on software engineering concepts
title_full A complexity lower bound based on software engineering concepts
title_fullStr A complexity lower bound based on software engineering concepts
title_full_unstemmed A complexity lower bound based on software engineering concepts
title_sort complexity lower bound based on software engineering concepts
publishDate 2013
url http://sedici.unlp.edu.ar/handle/10915/32381
work_keys_str_mv AT rojasparedesandres acomplexitylowerboundbasedonsoftwareengineeringconcepts
AT rojasparedesandres complexitylowerboundbasedonsoftwareengineeringconcepts
bdutipo_str Repositorios
_version_ 1764820469730508800

Ejemplares similares