3
$\begingroup$

I was thinking of the mandelbrot set. When you draw a picture of it at some resolution, you are able to get some idea of what it is, but there will be details that are lost.
Is there a way to quantify the amount of detail/complexity of an object? Is there a branch of math that studies this (I am aware of kolmogorov complexity)?
The mandelbrot set would be have a measure of complexity that is somehow absolute (infinite), I suppose.

$\endgroup$
5
  • 1
    $\begingroup$ It depends on what you mean by "complexity". Some of the tools used in fractal geometry are relevant, e.g. the "dimension" of an object tells us something about the complexity of that object. That being said, I really am not at all sure that I understand what you are asking for... $\endgroup$
    – Xander Henderson
    Feb 1, 2021 at 1:42
  • 2
    $\begingroup$ What's wrong with Kolmogorov? $\endgroup$ Feb 1, 2021 at 1:57
  • 1
    $\begingroup$ For sets in metric spaces (including fractals), there is a notion of Hausdorff dimension which (Wikipedia says) measures "roughness" of a set in a metric space. For sets which are "nice," the dimension agrees with what you'd expect. But the boundary of the Mandelbrot set has Hausdorff dimension 2, the same as the dimension of a (2-dimensional!) square. So, this boundary which naïvely seems 1-dimensional, can be seen as much more complex (it's 2 dimensional in this sense!). $\endgroup$
    – Stahl
    Feb 7, 2021 at 7:25
  • $\begingroup$ I want to also say that the complexity of the Mandelbrot set might be infinite if you measure in a certain sense, but you might also very reasonably expect it to be finite. Remember that fractals are self-similar -- so, while there is an infinite amount of detail in a fractal, the self-similarity and repetition might make it much less complex than it looks from a glance. After all, complex fractals like Julia sets are completely determined by specifying a single polynomial! $\endgroup$
    – Stahl
    Feb 7, 2021 at 7:28
  • $\begingroup$ The mandelbrot set would be have a measure of complexity that is somehow absolute (infinite) --- Since the Mandelbrot set is closed, it's about a trivial as possible from the standpoint of descriptive set theory. Thus, in the strictly increasing transfinite-sequence (whose length is uncountable) of collections of increasingly complex sets of points whose union consists of the Borel sets (see here), the Mandelbrot set is in the lowest level of complexity. And this is just the beginning . . . $\endgroup$ Feb 7, 2021 at 9:34

1 Answer 1

1
$\begingroup$

To the best of my knowledge, there isn't an overarching/unifying theory for this. There are some directions on this within Computational Complexity and Theoretical Computer Science that are worth considering.

  • As you said, Kolmogorov Complexity measures the length of the shortest program required to generate an object.

  • Descriptive complexity measures how succinctly we can express certain properties about a given object with respect to an underlying logic. For example, in first-order logic, we are interested in both the number of variables and the quantifier depth of a given expression. The descriptive complexity of an object is closely related to its Weisfeiler--Leman dimension (see for instance, the Cai-Furer-Immerman paper, https://people.cs.umass.edu/~immerman/pub/opt.pdf). Descriptive Complexity also seeks to characterize complexity classes in terms of logical definability. Immerman's text (https://www.springer.com/gp/book/9780387986005) on this is a good starting point. Grohe has a text on descriptive complexity for graphs (https://www.cambridge.org/core/books/descriptive-complexity-canonisation-and-definable-graph-structure-theory/BC758F6004BD96F6995D5F1EF1E29BAD).

  • One way to approach Automata Theory is to ask the following: given a class $\mathcal{C}$ of languages, what is the minimally powerful type of automaton needed to characterize $\mathcal{C}$? For example, regular languages are precisely captured by finite-state automata.

  • In circuit complexity, we study the size and depth of circuits, as well as the minimal complexity of circuits needed to compute a given function. One result on the latter is that $\textsf{Parity} \not \in \textsf{AC}^{0}$. This result provides a separation between $\textsf{AC}^{0}$ and $\textsf{ACC}^{0}$ (that is, $\textsf{AC}^{0} \subsetneq \textsf{ACC}^{0}$).

  • Edinah Gnang has a very recent paper on Partial Differential Encodings of Boolean Functions. This is an algebraic analogue of Kolmogorov Complexity (https://arxiv.org/pdf/2008.06801.pdf).

  • In Geometric Complexity Theory, one way to try and separate complexity classes $\mathcal{C}_{\text{Easy}}$ and $\mathcal{C}_{\text{Hard}}$ is by finding a module $T$ (think polynomials) that vanishes on every function in $\mathcal{C}_{\text{Easy}}$, but does not vanish on at least one function in $\mathcal{C}_{\text{Hard}}$. The Introduction and Preliminaries of Joshua A. Grochow's paper (https://link.springer.com/article/10.1007%2Fs00037-015-0103-x) serve as a nice introduction.

  • As was mentioned above, the dimension of a mathematical object is a measure of complexity.

Edit: Since Hausdorff Dimension was mentioned in one of the comments, it is worth pointing out that Hausdorff Dimension has close connections both to fractal geometry and Kolmogorov Complexity (e.g., https://arxiv.org/pdf/cs/0208044.pdf). Jack Lutz is an expert on measures of geometric dimension, including their connections to computational complexity and information theory (e.g., relationships to Kolmogorov Complexity). It would be worthwhile to check out some of his papers (http://web.cs.iastate.edu/~lutz/papers.html).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .