Complejidad para problemas de geometría elemental

Mostrar todas las versiones(3)

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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Krick, Teresa Elena Genoveva
Formato: Tesis Doctoral
Lenguaje:Español
Publicado: 1990
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n2317_Krick
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:tesis_n2317_Krick
record_format dspace
spelling todo:tesis_n2317_Krick2023-10-03T12:28:29Z Complejidad para problemas de geometría elemental Krick, Teresa Elena Genoveva 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. Fil: Krick, Teresa Elena Genoveva. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 1990 Tesis Doctoral PDF Español info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n2317_Krick
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv Español
description 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.
format Tesis Doctoral
author Krick, Teresa Elena Genoveva
spellingShingle Krick, Teresa Elena Genoveva
Complejidad para problemas de geometría elemental
author_facet Krick, Teresa Elena Genoveva
author_sort Krick, Teresa Elena Genoveva
title Complejidad para problemas de geometría elemental
title_short Complejidad para problemas de geometría elemental
title_full Complejidad para problemas de geometría elemental
title_fullStr Complejidad para problemas de geometría elemental
title_full_unstemmed Complejidad para problemas de geometría elemental
title_sort complejidad para problemas de geometría elemental
publishDate 1990
url https://hdl.handle.net/20.500.12110/tesis_n2317_Krick
work_keys_str_mv AT krickteresaelenagenoveva complejidadparaproblemasdegeometriaelemental
_version_ 1782030449005035520

Ejemplares similares