Catálogo de publicaciones - tesis
Título de Acceso Abierto
Complejidad para problemas de geometría elemental
Teresa Elena Genoveva Krick Joos Heintz
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
I-a) Sea Ω un cuerpo algebraicamente cerrado y sea K un subcuerpo de Ω. L nota el lenguaje de primer orden de Ω a constantes en K . Para cada fórmula prenexa Ф ϵ L, sean F1,...,Fs ϵ K [X1,...,Xn] los polinomios que aparecen en Ф. Se define |Ф|:= longitud de Ф |D|:= 2 + Σ 1≤i≤s gr Fi r := número de bloques de cuantificadores de Ф Se exhibe un algoritmo que elimina los cuantificadores de Ф, que funciona en tiempo secuencial D^n^cr y en tiempo paralelo n^cr(log2 D)^c (donde c es una. constante universal adecuada). Se muestra además que estas cotas son optimales. b) Se aplica el algoritmo de (a) para el cálculo eficiente del polinomio de Chow del radical de un ideal polinomial homogéneo débilmente unmixed. c) Se examina el algoritmo rápido de eliminación de cuantificadores sobre cuerpos real cerrados de J. Heintz, M.-F. Roy y P. Solernó para obtener cotas sobre los grados y el valor absoluto de los coeficientes de los polinomios que aparecen en la fórmula de salida. II-a) Sean F1,.. .,Fs ϵ Z[X1, . . .,Xn] polinomios cuasiconvexos de grado acotado por d ≥ 2, y sea a una cota para la longitud binaria de los coeficientes de F1,...,Fe. Se muestra que si el sistema F1 ≤ 0,...,F. ≤ 0 admite una solución entera, entonces existe tal solución con longitud binaria acotada por (sd)^cn (donde c es una constante universal). El caracter simplemente exponencial de la cota es intrínseco al problema. b) Se utiliza (a) para resolver con cotas similares el problema de hallar el ínfimo del conjunto {Fo(x) : x ϵ Z^n, F1(x) ≤ 0,...,F,(x) ≤ 0} si éste se realiza, para un polinomio Fo ϵ Z[X1,...,Xn] cuasiconvexo también.Palabras clave – provistas por el repositorio digital
No disponibles.
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 1990 | 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
1990
Información sobre licencias CC