Closer to the approach described in this paper,
and the one which in fact has largely inspired the present line of work,
is a range of theories based on the solution
space geometry of the underlying optimization problem.
This approach emerged in the statistical physics literature, specifically the study of spin glasses,
and more recently found its way to questions above and beyond statistical physics, in particular questions
arising in the context of studying neural networks as [1]}.
The general philosophy of this take on the algorithmic complexity
is that when the problem appears to be algorithmically hard, this somehow should be reflected
in the non-trivial geometry of optimal or near optimal solutions.
One of the earliest such approaches was formulated for the decision
problems, such as random constraint satisfaction problems (aka random K-SAT problem).
It links the algorithmic hardness with the proximity to the satisfiability phase transition threshold [2]},
[3]}, and the order (first vs second) of
the associated phase transition [4]}.
To elaborate, we need to introduce the
random K-SAT problem first. It is a Boolean constraint satisfaction
problem involving \(N\)  variables \(x_1,\ldots ,x_N\)  defined as a conjunction \(\Phi \)  of \(M\) 
clauses \(C_1\wedge C_2\wedge \cdots \wedge C_M\) , where each
clause \(C_j\)  is a disjunction of exactly \(K\)  variables from \(x_1,\ldots ,x_N\)  or their negation.
Thus, each \(C_j\)  is of the form \(x_{j,1}\vee \lnot x_{j,2}\vee \cdots \vee \lnot x_{j,K}\) .
An example of such a formula with \(N=10\) , \(M=4\)  and \(K=3\)  is say
\((x_2\vee \lnot x_5\vee x_6)\wedge (\lnot x_1\vee \lnot x_2\vee x_9)\wedge (\lnot x_6\vee x_8\vee \lnot x_{10})\wedge (\lnot x_3\vee x_2\vee x_7)\) .
A formula is called satisfiable if there exists an assignment of Boolean variables
\(x_i, 1\le i\le N\)  to values 0 and 1 such that the value of the formula is 1.
