Computabilidad de los conjuntos de Julia de polinomios hiperbólicos

Abstract

[eng] This work explores the intersection between dynamical systems and theoretical computer science, focusing on the computability of Julia sets. Due to the uncountable cardinality of the complex plane and the unstable, chaotic behavior that arises in holomorphic dynamics, the question arises whether these geometric structures of infinite complexity can be accurately represented by machines of a discrete, finite, and approximate nature.

The work details the affirmative answer to this question, proven by Mark Braverman: the Julia sets of hyperbolic polynomials are computable in polynomial time. To achieve this, we combine models of algorithmic complexity and complex geometry. The key to the resolution lies in the expansive property of these polynomials with respect to the hyperbolic metric, allowing us to construct control domains and linearly bound the escape time of the orbits.

[spa] Este trabajo explora la intersección entre sistemas dinámicos e informática teórica, enfocándose en la computabilidad de los conjuntos de Julia. Debido a la cardinalidad no numerable del plano complejo y al comportamiento inestable y caótico que aparece en dinámica holomorfa, surge la duda de si estas estructuras geométricas de infinita complejidad pueden ser representadas de forma exacta mediante máquinas de naturaleza discreta, finita y aproximada.

El trabajo detalla una respuesta afirmativa a esta cuestión, demostrada por Mark Braverman: los conjuntos de Julia de polinomios hiperbólicos son computables en tiempo polinómico. Para ello, combinamos modelos de complejidad algorítmica y geometría compleja. La clave de la resolución reside en la propiedad expansiva de estos polinomios respecto a la métrica hiperbólica, lo que permite construir dominios de control y acotar linealmente el tiempo de escape de las órbitas.

[cat] Aquest treball explora la intersecció entre els sistemes dinàmics i la informàtica teòrica, centrant-se en la computabilitat dels conjunts de Julia. Donada la naturalesa contínua del pla complex i el comportament inestable i caòtic que apareix en dinàmica holomorfa, sorgeix el dubte de si aquestes estructures geomètriques d’infinita complexitat poden ser representades computacionalment amb una precisió garantida mitjançant màquines de naturalesa discreta, finita i aproximada.

El treball detalla la resposta afirmativa a aquesta qüestió, demostrada per Mark Braverman: els conjunts de Julia de polinomis hiperbòlics són computables en temps polinòmic. Per a això, combinem models de complexitat algorítmica i geometria complexa. La clau de la resolució resideix en la propietat expansiva d’aquests polinomis respecte a la mètrica hiperbòlica, fet que permet construir dominis de control i fitar linealment el temps d’escapament de les òrbites.