Estaba pensando en el conjunto de Mandelbrot. Cuando se hace un dibujo de él con cierta resolución, es posible hacerse una idea de lo que es, pero habrá detalles que se pierden.
¿Hay alguna forma de cuantificar la cantidad de detalles/complejidad de un objeto? ¿Existe una rama de las matemáticas que estudie esto (conozco la complejidad de Kolmogorov)?
El conjunto de Mandelbrot tendría una medida de complejidad que es de alguna manera absoluta (infinita), supongo.
Respuesta
¿Demasiados anuncios?
ml0105
Puntos
8033
Hasta donde yo sé, no hay una teoría global/unificadora para esto. Hay algunas orientaciones al respecto dentro de la Complejidad Computacional y la Informática Teórica que merece la pena considerar.
-
Como has dicho, la complejidad de Kolmogorov mide la longitud del programa más corto necesario para generar un objeto.
-
La complejidad descriptiva mide lo sucintamente que podemos expresar ciertas propiedades sobre un objeto dado con respecto a una lógica subyacente. Por ejemplo, en la lógica de primer orden, nos interesa tanto el número de variables como la profundidad del cuantificador de una expresión dada. La complejidad descriptiva de un objeto está estrechamente relacionada con su dimensión de Weisfeiler-Leman (véase, por ejemplo, el artículo de Cai-Furer-Immerman, https://people.cs.umass.edu/~immerman/pub/opt.pdf ). La complejidad descriptiva también trata de caracterizar las clases de complejidad en términos de definibilidad lógica. El texto de Immerman ( https://www.springer.com/gp/book/9780387986005 ) sobre esto es un buen punto de partida. Grohe tiene un texto sobre la complejidad descriptiva de los grafos ( https://www.cambridge.org/core/books/descriptive-complexity-canonisation-and-definable-graph-structure-theory/BC758F6004BD96F6995D5F1EF1E29BAD ).
-
Una forma de abordar la teoría de los autómatas es preguntarse lo siguiente: dada una clase $\mathcal{C}$ de lenguajes, ¿cuál es el tipo de autómata mínimamente potente necesario para caracterizar $\mathcal{C}$ ? Por ejemplo, los lenguajes regulares son capturados con precisión por los autómatas de estado finito.
-
En la complejidad de los circuitos, se estudia el tamaño y la profundidad de los mismos, así como la complejidad mínima de los circuitos necesarios para calcular una función determinada. Un resultado sobre este último es que $\textsf{Parity} \not \in \textsf{AC}^{0}$ . Este resultado proporciona una separación entre $\textsf{AC}^{0}$ y $\textsf{ACC}^{0}$ (es decir, $\textsf{AC}^{0} \subsetneq \textsf{ACC}^{0}$ ).
-
Edinah Gnang tiene un artículo muy reciente sobre las codificaciones diferenciales parciales de las funciones booleanas. Se trata de un análogo algebraico de la complejidad de Kolmogorov ( https://arxiv.org/pdf/2008.06801.pdf ).
-
En la Teoría de la Complejidad Geométrica, una forma de intentar separar las clases de complejidad $\mathcal{C}_{\text{Easy}}$ y $\mathcal{C}_{\text{Hard}}$ es encontrando un módulo $T$ (piense en polinomios) que desaparece en cada función en $\mathcal{C}_{\text{Easy}}$ pero no desaparece en al menos una función en $\mathcal{C}_{\text{Hard}}$ . La Introducción y los Preliminares del documento de Joshua A. Grochow ( https://link.springer.com/article/10.1007%2Fs00037-015-0103-x ) sirven como una buena introducción.
-
Como se ha mencionado anteriormente, la dimensión de un objeto matemático es una medida de complejidad.
Editar: Ya que se ha mencionado la dimensión de Hausdorff en uno de los comentarios, conviene señalar que la dimensión de Hausdorff está estrechamente relacionada tanto con la geometría fractal como con la complejidad de Kolmogorov (por ejemplo, https://arxiv.org/pdf/cs/0208044.pdf ). Jack Lutz es un experto en medidas de dimensión geométrica, incluidas sus conexiones con la complejidad computacional y la teoría de la información (por ejemplo, las relaciones con la complejidad de Kolmogorov). Merece la pena consultar algunos de sus artículos ( http://web.cs.iastate.edu/~lutz/papers.html ).
