Registro:
Documento: | Tesis Doctoral |
Disciplina: | matematica |
Título: | Complejidad para problemas de geometría elemental |
Autor: | Krick, Teresa Elena Genoveva |
Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
Lugar de trabajo: | Instituto Argentino de Matemática (IAM)
|
Publicación en la Web: | 2017-03-01 |
Fecha de defensa: | 1990 |
Fecha en portada: | 1990 |
Grado Obtenido: | Doctorado |
Título Obtenido: | Doctor en Ciencias Matemáticas |
Departamento Docente: | Departamento de Matemáticas |
Director: | Heintz, Joos |
Idioma: | Español |
Formato: | PDF |
Handle: |
http://hdl.handle.net/20.500.12110/tesis_n2317_Krick |
PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n2317_Krick.pdf |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n2317_Krick |
Ubicación: | 002317 |
Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Krick, Teresa Elena Genoveva. (1990). Complejidad para problemas de geometría elemental. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n2317_Krick |
Resumen:
I-a) Sea Ω un cuerpo algebraicamente cerrado y sea K un subcuerpo de Ω. L notael lenguaje de primer orden de Ω a constantes en K . Para cada fórmula prenexa Ф ϵ L, sean F1,...,Fs ϵ K [X1,...,Xn] los polinomiosque aparecen en Ф. Se define |Ф|:= longitud de Ф |D|:= 2 + Σ 1≤i≤s gr Fir := número de bloques de cuantificadores de Ф Se exhibe un algoritmo que elimina los cuantificadores de Ф, que funciona entiempo 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 delradical de un ideal polinomial homogéneo débilmente unmixed. c) Se examina el algoritmo rápido de eliminación de cuantificadores sobre cuerpos realcerrados de J. Heintz, M.-F. Roy y P. Solernó para obtener cotas sobre los gradosy el valor absoluto de los coeficientes de los polinomios que aparecen en la fórmulade salida. II-a) Sean F1,.. .,Fs ϵ Z[X1, . . .,Xn] polinomios cuasiconvexos de grado acotado pord ≥ 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 ces una constante universal). El caracter simplemente exponencial de la cota esintrínseco al problema. b) Se utiliza (a) para resolver con cotas similares el problema de hallar el ínfimo delconjunto {Fo(x) : x ϵ Z^n, F1(x) ≤ 0,...,F,(x) ≤ 0} si éste se realiza, para unpolinomio Fo ϵ Z[X1,...,Xn] cuasiconvexo también.
Citación:
---------- APA ----------
Krick, Teresa Elena Genoveva. (1990). Complejidad para problemas de geometría elemental. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n2317_Krick
---------- CHICAGO ----------
Krick, Teresa Elena Genoveva. "Complejidad para problemas de geometría elemental". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 1990.https://hdl.handle.net/20.500.12110/tesis_n2317_Krick
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n2317_Krick.pdf