Catálogo de publicaciones - tesis
Título de Acceso Abierto
Complejidad de conjuntos semialgebraicos
Pablo L. Solerno Joos Heintz
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
Sea L el lenguaje de primer orden sobre cuerpos real-cerrados. Para cada fórmula ɸ є L si P c Z [x1,...,xn] es el conjunto de polinomios que aparecen en ɸ notamos σ (ɸ): = 2 + ΣpєP deg (P) y |ɸ| := longitud de ɸ. 1. Se exhibe un algoritmo que elimina cuantificadores en L (y en particular descompone cilíndricamente R^n). Para cualquier fórmula ɸ en n-variables dicho algoritmo funciona en tiempos: σ(ɸ)² °(n)+o(|ɸ|) (secuencial) y 2°(n)log2^4σ(ɸ)+O(log2|ɸ|) (paralelo). Se muestra además que estas cotas superiores son optimales. 2. Dado un conjunto semialgebráico A descrito por ecuaciones e inecuaciones sobre una familia finita de polinomios F c Z [x1,...,xn], se construye un sistema de representantes para las componentes convexas de A por medio de un algoritmo que funciona en tiempos: d^n°(¹) (secuencial) y (n log2^d) °(¹) (paralelo), donde d := ΣpєP deg P. 3. Se exhibe un algoritmo tal que, dada ɸ є L, sin variables libres y escrita en forma prenexa, con r := número de bloques de cuantificadores, se decide la verdad o falsedad de ɸ en tiempos: σ(ɸ)^n°(r) (secuencial) y n°(r) (log σ(ɸ))°(¹) (paralelo).Palabras clave – provistas por el repositorio digital
No disponibles.
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 1989 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
1989
Información sobre licencias CC