# How to calculate complexity in a high dimensional space?

Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong.

For a specific f(), I'm defining a term 'complexity', estimating how difficult is the given function to optimize. I attempted a solution in low dimension, but I might not be on the right track to generalize to n-dimn. This concept probably has a name and a better existing approximation, but here's what I have:

f(x) has input values bound [0, 5], x = [x1, x2, x3, x4...] (n-dimn), and f() outputs a single continuous value for 'success', bound [0, 1]

Example:

For input [x1, x2], calculate f(x) = y, and then relabel (x1, x2, y) as (x, y, z) for the plots below.

If it's easy to achieve an output of 1 through any random input, then you have a low complexity space.

An example f() space, where all input values result in z=1 (low complexity):

An example f() space, where only one input value results in z=1 (high complexity):

Complexity measured as volume enclosed between the xy-plane and the z-hyperplane seems valuable, but it alone does not work, because increasing volume at z=0.8 depth is 'worth more' than the same amount increased at 0.2 depth (in terms of optimizing for z=1). It's not just the z=1 region that is important as 'success', but also where z=0.9, z=0.8, etc. proportionally.

So what I've come up with so far is to compute a grid of inputs, and get their output values: i.e. f([0, 0])=0.0 f([0, 1])=0.3 f([0, 2])=0.2 ... then plot those to approximate the z-hyperplane. If I sum all the sample's z-values (0, .3, .2...) (and as the number of samples on the grid increases), it gives a nice sort of depth-weighted volume estimate.

There's a problem that local minima can cause increased volume (lower complexity), yet lead away and make it more difficult to navigate toward any deeper / global min's (higher complexity). (Weighted volume might handle this, but I'm unsure)

Example f() space where both have the same volume (picture's not exact, but you get it right? and I rotated axes, sry):

How can I incorporate that factor, that some points on the function increase volume, but the addition of that volume contributes less than if the volume was adjacent to a deeper space (in a similar function, ex. the f() on the right, above)? It seems like the critical feature that distinguishes those two hyperplanes is that the sign of the slope flips, where the negative slope leads into a local min, away from the global min, and the more frequently the sign flips, the harder the function will be to optimize.

If I iterate the grid rows and cols, and calculate the number of slope sign changes, that might be useful, or there might be a way to use trig to project a line and see what depth it intersects the hyperplane, but this is where I realized I need help.

My original idea was to define complexity as how resistant are the output values to fluctuations in the input values, given a specific input. So I have a decent estimate with my 'weighted-volume' calculation, but it's still lacking.

(1) Do you recognize the 'complexity' concept as another existing term?

I found 'fitness landscape analysis' in evolutionary optimization


(2) If not, can I improve beyond 'weighted-volume'?

(3) Will this work for higher dimensions?

As far as I have understood, you aim to develop a framework to capture the hardness of combinatorial problems in 3D. However, there are major problems in your question.

Your first sentence lacks a couple of technical definitions:

For a specific f(), I'm defining a term 'complexity', estimating how difficult is the given function to optimize.

First, and the most important of all, you should have a well defined complexity measure in order to adapt the term. Then, another sentence makes your question even more complicated:

If it's easy to achieve an output of 1 through any random input, then you have a low complexity space.

Here, you need to have a clear definition of easy. Is it in terms of computational complexity? If so, how do you measure the input size?

After this sentence, I am honestly lost:

Complexity measured as volume enclosed between the xy-plane and the z-hyperplane seems valuable, but it alone does not work, because increasing volume at z=0.8 depth is 'worth more' than the same amount increased at 0.2 depth (in terms of optimizing for z=1). It's not just the z=1 region that is important as 'success', but also where z=0.9, z=0.8, etc. proportionally.

What does it mean to worth more? What is increasing, and what is decreasing? What are yoou trying to optimize?

All in all, although I could not understand your question well enough, I would go ahead and say that there are different ways to measure "complexity" in different dimensions, unless you invent a brand new system to represent the coordinates.

• Sorry you didn't get much from the post, I'll try to explain. (1) Of course the post lacks a good definition for 'complexity', that is the entire goal of the post, to define the term computationally. (2) 'Easy' does need to be defined too, and I start in the post to look at 'ease' as how much 'volume' of the solution space leads towards or is at a depth where z=1 (ie. a global minimum has been found' (maximum actually). What do you mean by 'measure the input size'? Oct 22 '20 at 16:25
• Complexity is a broadly used term, which usually refers to the computational complexity. To put very roughly, computational complexity is measured by the resource usage w.r.t. the input size. So, if you are to mention complexity, first you need to tell with respect to what. Oct 22 '20 at 21:25