El Proyecto CHATA

El proyecto CHATA V. ´ Alvarez, J.A. Armario, M.D. Frau, R. Gonz´alez–D´ıaz, M.J. Jim´enez, P. Real y B. Silva Dpto. Matem´atica Aplicada I (Universidad de Sevilla) Avda. Reina Mercedes, s/n. CP: 41012 Sevilla (Espa˜na) E-mails: {valvarez,armario,mfrau,rogodi,majiro,real,silva}@cica.es Resumen En este art´ıculo, se pretende dar una visi´on general y lo m´as divulgativa posible sobre los prop´ositos y objetivos del proyecto de investigaci´on CHATA (Computational Homological Algebra and Algebraic Topology and Applications), en el que estamos involucrados siete investigadores del Departamento de Matem´atica Aplicada Ide la Universidad de Sevilla. Este proyecto tiene como objetivo esencial el desarrollo de procesos algor´ıtmicos en Topolog´ıa Algebraica y´ Algebra Homol´ogica de inter´es pr´actico. Es necesario enfatizar que nuestra motivaci´on no es tan s´olo obtener soluciones positivas al problema de la computabilidad en estas ´areas (problema ya de por s´ı delicado), sino que fundamentalmente nuestra preocupaci´on es la misma que Tangora [48] mostraba en los a˜nos ochenta: “convertir, siempre que sea posible, soluciones intratables desde el punto de vista pr´actico debido a la enorme complejidad que presentan, en algoritmos tratables y viables. Ante tal meta, en una primera etapa es obligado plantearse, por una parte, un procedimiento general para considerar constructivamente los m´etodos usados en estos campos y, por otra, una teor´ıa de complejidad en estas ´areas que nos permita evaluar adecuadamente la eficiencia de los algoritmos, para despu´es intentar realizar un refinamiento de estos. 1 Introducci´on La Topolog´ıa Algebraica analiza transformaciones de datos continuos a discretos. Una primera fase en este proceso de discretizaci´on fue el establecer invariantes algebraicos asociados a los espacios topol´ogicos. Dichos invariantes son ´utiles algebraicos que nos ayudan a distinguir espacios topol´ogicos no–homeomorfos. El proyecto CHATA hace especial hincapi´e en el dise˜no de algoritmos de c´alculo de invariantes que sean lo m´as eficientes posible. La tarea te´orica es dura debido a los elevados costes computacionales que, en general, presentan estos procesos. No estamos tan interesados en obtener resultados a´un no conocidos y originales en Topolog´ıa Algebraica como en establecer una cimentaci´on algor´ıtmica s´olida en este campo. Esta propuesta tiene cabida dentro de otra iniciativa m´as amplia que nuestro grupo desarrolla en el contexto de la emergente ´area de Topolog´ıa Computacional. 52 Actas de EMA. Sevilla,13-17 de noviembre de 2000 Por supuesto, el objetivo ´ultimo de este proyecto es el de implementar en m´aquina inform´atica los algoritmos dise˜nados por el grupo, usando lenguajes de programaci´on como C+ + o LISP (donde es posible trabajar en un marco de programaci´on fuertemente orientada a objeto) y/o programas comerciales como Mathematica, MAPLE, etc. Para esta tarea, ya contamos con la ayuda de investigadores expertos en este contexto como son los profesores Julio Rubio (Universidad de Zaragoza) y Francis Sergeraert (Universidad de Grenoble I). M´as concretamente, en colaboraci´on con el grupo de investigaci´on que dirige el profesor Julio Rubio coordinamos en los pr´oximos tres a˜nos, un proyecto de investigaci´on de la Direcci´on General de Ense˜nanza Superior e Investigaci´on Cient´ıfica (PB98-1621-C02-02) y en donde la l´ınea de acci´on que propone CHATA est´a completamente integrada. El proyecto CHATA requiere un trabajo interdisciplinar bien organizado. ´ Este se intentar´a mover entre campos tan extensos como Topolog´ıa Computacional, ´ Algebra Computational, ´ Algebra Homol´ogica, Teor´ıa de Grupos, Topolog´ıa Algebraica, Teor´ıa de Dise˜nos Combinatoriales, Sistemas Din´amicos, C´alculo Secundario (y aproximaciones algebraicas a las ecuaciones diferenciales en derivadas parciales no–lineales) y F´ısica Cohomol´ogica. Todas estas ´areas, algunas de ellas aparentemente disconexas entre s´ı, est´an ligadas por una visi´on unificada a trav´es de nuestro proyecto. En este art´ıculo, no pretendemos ser exhaustivos a la hora de concretar todos los objetivos que nos marcamos en esta iniciativa sino explicar a grandes trazos nuestra forma de trabajar para establecer m´etodos computacionales en distintos problemas de Topolog´ıa Algebraica y ´ Algebra Homol´ogica. En primer lugar, comentamos someramente el problema de la computabilidad, al tiempo que se aportan soluciones algor´ıtmicas de ´ındole general para tratar una gran cantidad de cuestiones en Topolog´ıa Algebraica y ´ Algebra Homol´ogica. Proseguimos dando una idea del problema de la complejidad en este ´ambito, para posteriormente meternos de lleno en los objetivos a corto y medio plazo que pretende alcanzar el proyecto CHATA. Operaciones cohomol´ogicas, homolog´ıa de fibrados simpliciales (siendo los factores conjuntos simpliciales significativos), grupos de homotop´ıa, homolog´ıa de ´algebras diferenciales graduadas conmutativas y homolog´ıa de grupos son los t´opicos sobre los que aqu´ı discutiremos someramente desde una perspectiva computacional. 2 Computabilidad en Topolog´ıa Algebraica Comencemos con un problema en Topolog´ıa Digital 2–dimensional. Supongamos que tenemos un objeto Aen el plano y que realizamos un proceso de digitalizaci´on del mismo. La digitalizaci´on que usaremos es la utilizada en [22], la cual aproxima muchos procesos de digitalizaci´on reales. Este m´etodo est´a modelado como una aplicaci´on de conjuntos continuos representando objetos reales a conjuntos discretos representando im´agenes digitales. Usando un sensor real, la digitalizaci´on de A, la definimos con respecto a un mallado de cuadrados que recubre R2. Un cuadrado es un pixel negro si y solo si el cociente del ´area del campo “visto” por el sensor en un determinado cuadrado entre el ´area total del cuadrado correspondiente es mayor que alg´un valor V. Alvarez et al. “El proyecto CHATA” 53 prefijado α. Supongamos que escogemos un αtal que la digitalizaci´on de A, que notamos Dig(A), “preserva la topolog´ıa” . Por “preservaci´on de la topolog´ıa” se entender´a que Aes homot´opicamente equivalente a Dig(A) (esta definici´on procede de Gross y Latecki [22]). Esto significa, en particular, que ambos objetos presentan el mismo n´umero de componentes conexas y el mismo n´umero de “agujeros”. Usando la terminolog´ıa propia de la Topolog´ıa Algebraica cl´asica, sus correspondientes grupos de homolog´ıa en grado cero y uno son isomorfos y, por tanto, la caracter´ıstica de Euler de ambos objetos es la misma. Desde una perspectiva computacional, esto quiere decir que el c´alculo de la homolog´ıa del objeto continuo Apuede hacerse via la del objeto digital Dig(A) y para este ´ultimo hay algoritmos eficaces de etiquetado y obtenci´on de dichos invariantes. Lo cierto es que las cosas ya no son tan f´aciles si nos interesamos por invariantes m´as complejos que el de homolog´ıa de un objeto digital 2D, trabajamos en dimensiones superiores y en el marco m´as general de la Topolog´ıa Algebraica cl´asica (donde la mayor´ıa de los objetos que se maneja son “infinitos”). No s´olo nos encontramos con problemas resolubles algor´ıtmicamente pero que no admiten una soluci´on, digamos, eficiente, sino que aparecen una significativa cantidad de problemas decidibles, es decir, problemas para los cuales no existe ning´un algoritmo que los resuelva. Ejemplos relevantes de esto ´ultimo son la decidibilidad del problema de las palabras [35] ´o la decidibilidad del problema del homeomorfismo entre dos n-variedades combinatoriales compactas con n≥4 [33]. Dentro de las teor´ıas que han propuesto un marco algor´ıtmico general en Topolog´ıa Algebraica y que han aportado soluciones efectivas para amplias partes de este ´area, podemos destacar fundamentalmente dos: la Topolog´ıa Algebraica Efectiva [45] y la teor´ıa de Homolog´ıa Efectiva [44]. En la primera se destaca la idea de que las sucesiones exactas (restringiendo el ´ Algebra Homol´ogica a grupos abelianos finitamente generados), son susceptibles de un tratamiento algor´ıtmico. En la segunda, se retoma el “modus operandi” de los matem´aticos Eilenberg y Mac Lane [14, 15] en los a˜nos 50 (que trabajaban en un contexto simplicial y con equivalencias de homotop´ıa expl´ıcitas), se contin´ua con un tratamiento algor´ıtmico adecuado de conjuntos infinitos y con una ulterior codificaci´on e implementaci´on. En el proyecto CHATA, seguiremos la mayor´ıa de las veces la l´ınea de acci´on perfilada por la Teor´ıa de la Homolog´ıa Efectiva, analizando detalladamente la complejidad de los procesos, de cara a determinar de antemano la potencia de c´alculo de sus posibles implementaciones y a proponer posteriores refinamientos. En otras palabras, en el trabajo que desarrolla nuestro grupo, no estamos s´olo interesados en problemas de decidibilidad en Topolog´ıa Algebraica, sino esencialmente en obtener procesos algor´ıtmicos de c´omputo de invariantes que sean lo m´as “razonables” posible, tanto en tiempo como en espacio. En la secci´on siguiente, explicaremos m´as detalladamente este calificativo de “razonable”. 54 Actas de EMA. Sevilla,13-17 de noviembre de 2000 3 El problema de la complejidad en Topolog´ıa Algebraica El problema que nos ocupa ahora es el de establecer una teor´ıa de complejidad apropiada en el ´ambito de la Topolog´ıa Algebraica Efectiva o Constructiva que nos permita clasificar los problemas decidibles en una escala de eficiencia. Deseamos ahora trabajar en un ambiente puramente combinatorial en el que podamos describir de manera expl´ıcita el traspaso de informaci´on entre objetos geom´etricos y algebraicos. Para ello nos situamos en el contexto de la Topolog´ıa Simplicial, donde los objetos b´asicos son conjuntos graduados en los enteros no negativos y dotados de dos tipos de operadores: operadores de cara (con claro significado geom´etrico) y de degeneraci´on (sin transcripci´on geom´etrica pero fundamentales a la hora de reconstituir la Geometr´ıa a partir del ´ Algebra). Estos objetos son llamados conjuntos simpliciales. Es inmediato asociar a un conjunto simplicial X, un m´odulo graduado C(X) dotado de un operador d, llamado diferencial, que disminuye el grado de uno y tal que d◦d= 0. A partir de este m´odulo diferencial graduado se puede extraer toda la informaci´on homol´ogica de X. Analicemos el problema de la complejidad en Topolog´ıa Algebraica mediante un ejemplo relevante en este area: una contracci´on Eilenberg-Zilber. Esta equivalencia de homotop´ıa es una terna de morfismos (f, g, h) que liga un producto ´algebro-geom´etrico C(X×Y) con uno puramente algebraico C(X)⊗C(Y), y que nos permite expresar la homolog´ıa de un producto cartesiano de conjuntos simpliciales en t´erminos de las homolog´ıas de los factores. Estamos interesados en medir la “eficiencia” de los morfismos componentes de esta contracci´on a la hora de evaluarlos sobre un elemento homog´eneo de grado ndel correspondiente m´odulo diferencial graduado. Consideremos que el tama˜no de la instancia sea n, tomemos como operaciones elementales los operadores de cara y de degeneraci´on de los conjuntos simpliciales XeY. Con estas premisas, podemos afirmar que el morfismo f:C(X×Y)→C(X)⊗C(Y) act´ua en tiempo O(n2), y que g:C(X)⊗C(Y)→C(X×Y) y h:C(X×Y)→C(X×Y) dan una respuesta en tiempo O(2n) . Un resultado pr´acticamente id´entico a ´este lo conseguimos a la hora de analizar la complejidad en espacio de la evaluaci´on de estos morfismos. Estos resultados son previsibles si precisamos que fno es m´as que una aproximaci´on simplicial al operador diagonal y que gyhpermiten reconstituir la Geometr´ıa a partir de informaci´on puramente algebraica. Adem´as, este comportamiento es el mismo para todas las contracciones que van de C(X×Y) a C(X)⊗C(Y). Por tanto, la dificultad que conlleva manejar los morfismos gyhde una contracci´on Eilenberg-Zilber es esencial. Por otra parte, contracciones de tipo Eilenberg-Zilber aparecen casi por doquier en los procesos de c´alculo de invariantes, lo que plantea un panorama global bastante desalentador. En un intento de simplificaci´on, podemos decir que el objetivo fundamental del proyecto CHATA es evitar (en la manera de lo posible) la naturaleza exponencial de los morfismos gyhde una contracci´on Eilenberg-Zilber, a la hora de dise˜nar algoritmos de c´alculo de invariantes. En las siguientes secciones veremos que dicho prop´osito lo hemos conseguido en el caso de las operaciones cohomol´ogicas de Steenrod y de la homolog´ıa de ´algebras diferenciales V. Alvarez et al. “El proyecto CHATA” 55 graduadas conmutativas (abreviadamente, ADGCs). Finalmente, la maquinaria que nos provee las contracciones sugiere nuevas perspectivas y aproximaciones a problemas cl´asicos de Topolog´ıa Algebraica y ´ Algebra Homol´ogica. No obstante, esta idea no es novedosa: como ya hemos comentado anteriormente, Eilenberg y Mac Lane trabajaban ya de esta peculiar forma. Una herramienta importante en este contexto es el de perturbaci´on de contracciones. La Teor´ıa de Perturbaci´on Homol´ogica ([23], [24]) es una t´ecnica sistem´atica y algor´ıtmicamente eficaz (por ejemplo, la teor´ıa de la Homolog´ıa Efectiva hace un continuo uso de ella) para la transferencia de estructuras de un objeto a otro salvo homotop´ıa; constituye un ´util poderoso para obtener DG-m´odulos que representen un tipo de homotop´ıa dado. El elemento m´as importante de esta teor´ıa de perturbaci´on es el Lema de Perturbaci´on B´asico, que puede verse como un verdadero algoritmo y que tiene como datos de entrada una contracci´on (f, g, h) entre dos DG-m´odulos (N, dN) y (M, dM), y una perturbaci´on δ:N∗→N∗−1(es decir, cumple que (dN+δ)(dN+δ) = 0), y como dato de salida una nueva contracci´on (fδ, gδ, hδ) de (N, dN+δ) a (M, dM+dδ), donde los m´odulos graduados subyacentes no han sufrido variaciones y s´olo se modifican las diferenciales y los morfismos integrantes de la contracci´on. Por ejemplo, el morfismo dδ:M∗→M∗−1presenta la siguiente f´ormula: dδ=fδg +fδhδg +fδhδhδg +. . . Obs´ervese que la suma anterior puede ser, en principio, infinita. En las secciones siguientes, mostraremos la potencia de este m´etodo algebraico de punto fijo a la hora de algoritmizar procesos en Topolog´ıa Algebraica y ´ Algebra Homol´ogica. De cara a dar una perspectiva m´as amplia del problema de la complejidad en Topolog´ıa Algebraica, analizamos ahora la perturbaci´on de una contracci´on EilenbergZilber (f, g, h). Si usamos como dato de perturbaci´on un morfismo δque act´ue en tiempo polinomial, es obvio que el c´alculo de dδsobre un elemento muestra un enorme gasto computacional, debido a que en cada sumando (salvo el primero) de su f´ormula aparece reiteradamente el operador de homotop´ıa hde dicha contracci´on. Este escollo, consustancial a la transmisi´on de informaci´on ´algebro-geom´etrica, puede ser evitado en determinadas situaciones, como veremos a continuaci´on. 4 Operaciones cohomol´ogicas desde una perspectiva computacional Si los grupos de homolog´ıa y cohomolog´ıa son apropiadas generalizaciones del invariante algebraico m´as inmediato (que es el n´umero de componentes conexas de un espacio), las operaciones cohomol´ogicas son morfismos entre los grupos de cohomolog´ıa que conmutan con homomorfismos inducidos de aplicaciones continuas. Esta 56 Actas de EMA. Sevilla,13-17 de noviembre de 2000 maquinaria es ´util cuando la estructura de espacio vectorial graduado y el producto cup que presenta la cohomolog´ıa fallan a la hora de distinguir dos espacios topol´ogicos no homeomorfos. Los cuadrados y potencias reducidas de Steenrod constituyen una clase extremadamente importante de operaciones cohomol´ogicas, no s´olo en Topolog´ıa Algebraica sino tambi´en en el area de m´etodos simpliciales del ´ Algebra Homol´ogica (cohomolog´ıa de grupos, cohomolog´ıa de Hochschild, . . . ). Existen varios m´etodos de construcci´on para estas operaciones. Uno de ellos consiste en construirlas haciendo uso de la cohomolog´ıa de los espacios de Eilenberg-Mac Lane (espacios de los que posteriormente hablaremos m´as detalladamente). Otro m´etodo consiste en determinar una familia de morfismos {Di}que“miden” la falta de conmutatividad del producto cup a nivel de cocadenas. En Topolog´ıa Algebraica cl´asica, la existencia de dicha sucesi´on de morfismos est´a garantizada por el m´etodo de los modelos ac´ıclicos [13]. En [39] y [20], se presenta un proceso alternativo para obtener la f´ormula expl´ıcita de los Di. M´as concretamente, en [39], se da una formulaci´on para cada Dien t´erminos de los morfismos componentes de una contracci´on Eilenberg-Zilber (f, g, h). Pero este nivel de descripci´on no es suficiente desde un punto de vista computacional. Por una parte, los morfismos componentes de la contracci´on anterior se definen en t´erminos de operadores cara y degeneraci´on del conjunto simplicial Xde partida. Por otra parte, en la f´ormula de cada Disiempre est´a envuelto el operador de homotop´ıa h. En consecuencia, si queremos expresar Dien t´erminos de operadores cara y degeneraci´on de X, en principio obtenemos que el n´umero de sumandos que aparecen en la f´ormula para un Dievaluado sobre un elemento de grado nes exponencial. Por tanto, un algoritmo que se dise˜nara a partir de esta formulaci´on no ser´ıa de mucho inter´es pr´actico. En [20], se simplifican substancialmente estas f´ormulas para el caso de productos cup-iy cuadrados de Steenrod, redescubri´endose y clarific´andose en un contexto combinatorial general el trabajo germinal (y actualmente bastante olvidado) de Norman Steenrod en 1947 [47]. Dicha simplificaci´on se basa en el hecho de que toda composici´on de operadores cara y degeneraci´on de un conjunto simplicial puede ser normalizada, es decir, expresada en una forma “can´onica”. Trabajando as´ı, obtenemos una descripci´on simplicial econ´omica de estos invariantes (v´eanse [18] y [19] para un estudio de la complejidad de evaluaci´on de estas operaciones). Adem´as, un tratamiento similar al anterior para potencias reducidas de Steenrod es factible a la luz del trabajo preliminar realizado en [20]. Como muestra de esta viabilidad, limit´emonos a decir que, por ejemplo, una primera medida de la complejidad computacional a la hora de evaluar la potencia reducida Pp 1(c) aplicada a un q-cociclo cqsobre un elemento de grado pq −1, puede venir dada por el n´umero de operadores de cara tomando parte en la f´ormula, que es p(p−1)q[(p−1)q−1] [21]. Es obvio que en el caso de que Xtenga un n´umero finito de s´ımplices no degenerados en cada grado, nuestro m´etodo puede ser visto como un verdadero algoritmo para calcular esta operaci´on cohomol´ogica. Por ejemplo, si el n´umero de s´ımplices no degenerados en cada X`es O(`) y cada operador de cara de Xes evaluado en tiempo constante, la eficiencia de nuestro algoritmo para calcular Pp 1(cq) is O(p4q3). V. Alvarez et al. “El proyecto CHATA” 57 Actualmente, disponemos de una formulaci´on simplicial en t´erminos exclusivamente de operadores cara para un gran n´umero de potencias reducidas de Steenrod y de ciertas operaciones cohomol´ogicas secundarias. Un objetivo a corto plazo del proyecto CHATA es finalizar el cuadro de descripciones expl´ıcitas de las operaciones cohomol´ogicas primarias y secundarias m´as relevantes de la Topolog´ıa Algebraica Cl´asica. Ya hemos comentado que esta t´ecnica muestra una falta de novedad en lo concerniente a productos cup-iy cuadrados de Steenrod. Ahora bien, con respecto a las potencias reducidas de Steenrod no hemos encontrado ninguna referencia en la literatura en el que se perfilen sus f´ormulas expl´ıcitas a nivel de cociclos. La perspectiva que mostramos de las operaciones cohomol´ogicas desde el punto de vista de la Teor´ıa de Perturbaci´on Homol´ogica es novedosa y fruct´ıfera y tenemos la convicci´on de que en un futuro cercano y trabajando de este modo, llegaremos a tener descritas operaciones cohomol´ogicas terciarias a nivel de complejos de cocadenas. Otro punto interesante de este trabajo es el meramente did´actico, ya que nos permite ver operaciones cohomol´ogicas “desnudas” a nivel combinatorial y, sin argumentos intermedios que difuminen su naturaleza computacional. Con estos resultados podemos ser optimistas y creemos que representan un primer paso en una previsible poderosa interrelaci´on entre las ´areas de la Topolog´ıa y el ´ Algebra Computacionales, donde los problemas de determinaci´on de operaciones en Cohomolog´ıa se reduzcan esencialmente a una simple cuesti´on de derrecursificaci´on de f´ormulas. Veremos que este fen´omeno no es un hecho aislado y que podemos obtener algoritmos razonables en otros ´ambitos, como es el de la homolog´ıa de las ADGCs. 5 Ataque algor´ıtmico al c´alculo de la homolog´ıa de “productos” de espacios primos en homotop´ıa Los espacios de Eilenberg-Mac Lane K(π, n) que dependen de un grupo abeliano finitamente generado y de un entero positivo, son espacios “primos” en homotop´ıa, en el sentido de que todo conjunto simplicial puede ser visto en forma factorizada como un producto cartesiano torcido de espacios de este tipo. Como ya apunt´abamos antes, el proyecto CHATA sigue como l´ınea de acci´on la esgrimida por la firma Eilenberg y Mac Lane en los a˜nos 50 ([14],[15]), donde el punto de partida lo aportaba la Topolog´ıa Simplicial, la informaci´on homol´ogica ven´ıa medida en forma de equivalencias de homotop´ıa expl´ıcitas y las herramientas algebraicas que usaban eran las que permit´ıan combinar, componer o perturbar dichos datos para obtener otros m´as complejos. Henri Cartan en 1964 (v´ease [12] para tener una mayor pespectiva hist´orica) dio una respuesta completa al c´alculo de los grupos de homolog´ıa de dichos espacios. El trabajo de traducci´on de este c´omputo a la forma de algoritmo es sencillo, pero la posterior reutilizaci´on de esta informaci´on de cara a obtener la homolog´ıa de productos cartesianos torcidos de espacios de Eilenberg-Mac Lane se nos antoja llena 58 Actas de EMA. Sevilla,13-17 de noviembre de 2000 de dificultades t´ecnicas y sutilidades te´oricas (sin mencionar las posibles deficiencias y limitaciones, sobre todo problemas de extensi´on, que presenta el desarrollo de un m´etodo constructivo a partir de estas premisas). Para poder dise˜nar un algoritmo de c´alculo directo en este sentido, nos resulta imprescindible el uso de la maquinaria sobre contracciones establecida por Eilenberg y Mac Lane y de la Teor´ıa de Perturbaci´on Homol´ogica. En [41], se establece informaci´on homol´ogica en t´erminos de contracciones sobre los “peque˜nos” complejos de Cartan, que nos permite trasladar c´omodamente el m´etodo de Cartan-Moore para obtener los grupos de homolog´ıa de cualquier K(π, n) al contexto de la Teor´ıa de Perturbaci´on Homol´ogica. En estas condiciones, la pregunta que nos hacemos es la siguiente: ¿qu´e podemos decir de la homolog´ıa de un fibrado simplicial (producto cartesiano torcido o, m´as abreviadamente, PCT) K(π, n)×τK(π0, n0), con fibra y base siendo espacios de Eilenberg-Mac Lane?. M´as concretamente, ¿es posible establecer un algoritmo de c´alculo razonable de sus grupos de homolog´ıa? Un primer algoritmo de c´alculo ha sido planteado en [2]. Sin embargo, este m´etodo, debido a la elevada complejidad que presenta, no lo consideramos viable a efectos de implementaci´on. El mayor gasto computacional de dicho m´etodo estriba en el proceso de perturbaci´on de la contracci´on Eilenberg-Zilber de C(K(π, n)×K(π0, n0)) aC(K(π, n)) ⊗C(K(π0, n0)), usando como dato de perturbaci´on el producido por el operador de torsi´on geom´etrica τen la diferencial del PCT. En otras palabras, el instalar una cocadena de torsi´on algebraica t:C(π0, n0)→C(π, n) en el producto tensorial C(K(π, n)⊗tC(K(π0, n0) que nos proporcione la misma informaci´on homol´ogica que el PCT de partida es el proceso m´as costoso. Por una parte, el optimizar el c´alculo de ty, por otra, el hecho de que podamos enriquecer nuestro algoritmo con t´ecnicas de preservaci´on de estructuras de ´algebras, A∞-co´algebras y cocadenas de torsi´on hacen que las expectativas de establecer un m´etodo computacional “tratable” para ese c´alculo sean halag¨ue˜nas. Finalmente, la obtenci´on de un resultado algor´ıtmico positivo para este proceso de “multiplicaci´on” repercutir´ıa inmediatamente en una mejora ostensible de la eficiencia del algoritmo te´orico de c´alculo de grupos de homotop´ıa (especificado en los art´ıculos [38] y [40]). 6 ¿Un sistema de c´alculo formal para la homolog´ıa de DG-´algebras conmutativas? El c´alculo de la homolog´ıa de ´algebras es un problema cl´asico en ´ Algebra Homol´ogica. Entenderemos por homolog´ıa de un ´algebra A, la homolog´ıa del m´odulo diferencial graduado ¯ B(A), llamado construcci´on bar reducida de A. Este objeto puede verse como una inversa formal de A. De esta forma, obligamos al producto del ´algebra A a aparecer en el c´alculo homol´ogico. Ahora bien, frecuentemente la construcci´on bar se presenta intratable desde un punto de vista computacional, debido al gran n´umero de generadores que posee. Hay veces, sin embargo, donde es posible establecer una equivalencia de homotop´ıa expl´ıcita (f, g, h) entre la construcci´on bar de un ´algebra V. Alvarez et al. “El proyecto CHATA” 59 diferencial graduada Ay otra construcci´on “m´as sencilla” H, es decir, con un menor n´umero de generadores (Hes un “peque˜no” modelo homol´ogico de A). Este es el caso de las ´algebras diferenciales graduadas libres conmutativas, que pueden verse en forma “factorizada” como productos tensoriales torcidos (o PTTs) de ´algebras exteriores y polinomiales. A su vez, las construcciones bar reducida de est´as ´ultimas ´algebras admiten contracciones hacia ADGCs “peque˜nas” (estas ´ultimas siendo tambi´en PTTs de ´algebras simples). Estas contracciones son composiciones de otras m´as simples, entre las cuales se ven envueltas contracciones de tipo Eilenberg-Zilber. Es en este ´ambito donde ya hemos planteado un primer algoritmo de c´alculo (v´ease [4]), el cu´al presenta problemas de complejidad que pasamos ahora a detallar. Consideremos como datos de entrada una secuencia creciente de enteros no-negativos n1≤n2≤. . . ≤nq(que expresan el grado de los generadores de las ´algebras exteriores y polinomiales que conforman el producto tensorial torcido de ´algebras de partida) y el valor de la diferencial de este PTT sobre cada generador. Este proceso da como salida los valores de la diferencial perturbada dδpara cada generador del ´algebra H. S´olo es necesario conocer dδsobre los qgeneradores del ´algebra y no sobre todo elemento de H, ya que utilizamos una herramienta refinada de perturbaci´on de ´algebras (la teor´ıa de la semi-completitud [41]). Ahora bien, ya hemos expresado anteriormente que el c´alculo de dδsobre un elemento de grado nen principio requiere como m´ınimo un tiempo exponencial. Este obst´aculo lo podemos salvar conjugando la teor´ıa de la semi-completitud con la t´ecnica, que nosotros hemos bautizado, de inversiones ([41], [7]). La t´ecnica de inversiones nos permite afirmar que, a la hora de evaluar un sumando fδhδ · · · hδg de dδ sobre un elemento cualquiera, s´olo es necesario tener en cuenta un n´umero polinomial de sumandos en cada aplicaci´on del operador de homotop´ıa h, ya que para el resto se tiene la certeza (usando argumentos de filtraciones) de que finalmente su evaluaci´on abocar´a en cero. Finalmente, el iniciar esta maquinaria con un preprocesamiento adecuado de la diferencial del ´algebra de partida Arevierte en el dise˜no de un algoritmo mejorado con respecto al inicial. El objetivo de CHATA en este ´area es la implementaci´on en m´aquina inform´atica de dicho algoritmo de c´alculo de homolog´ıa de ADGCs. Una vez realizado , el c´alculo de la n-homolog´ıa (con n≥2) y homolog´ıas de Harrison, de Hochschild y c´ıclica de ADGCs [32] aparecen factibles de ser atacados [5]. 7 Homolog´ıa de grupos y matrices estructuradas La determinaci´on de modelos homol´ogicos computables de grupos discretos se presenta abordable desde la ´optica de la Teor´ıa de Perturbaci´on Homol´ogica. Es bien sabido que la homolog´ıa de un grupo Gpuede ser vista (desde el punto de vista geom´etrico) como la homolog´ıa de un espacio de Eilenberg-Mac Lane K(G, 1). Por tanto, parece claro que las t´ecnicas de perturbaci´on deber´ıan proporcionar ideas para el dise˜no de algoritmos de c´alculo de la homolog´ıa de grupos. Este camino ya ha sido explorado fruct´ıferamente por Lambe y Stasheff [31], Huebschmann [27, 28], Rubio [43] y otros