Method of Modeling Problem Complexity

Question

Is there a standard way to model the complexity of a mathematical problem? If so, what are the best online resources to learn more about it?

Honestly don't have an even a basic way to model the complexity of a problem other than "depth" of concepts required to solve the problem and the smallest number of steps require to reach an answer. For example, "1+1=2" I would venture to guess is less complex than "1x2=2".

Answer 1

Computational Complexity?

It is indeed faster for a computer to perform addition than multiplication.

Answer 2

The complexity of the flow of information is one measure for the complexity of a mathematical problem. I will try to explain by example what I mean by this. Let's assume that we want to solve $F(x_1,\ldots,x_n)=0$ for $x_1,\ldots,x_n$.

1. In the simplest case, each $x_i$ can be computed completely independent of the other $x_j$.

2. More interesting is the case where $x_i$ can be computed based only on $x_1,\ldots,x_{i-1}$ and completely independent from $x_{i+1},\ldots,x_n$.

3. The LU decomposition of a matrix (=Gaussian elimination) reduces $F(x_1,\ldots,x_n)=0$ to the form $L(y_1,\ldots,y_n)=0$ and $U(x_1,\ldots,x_n)=R(y_1,\ldots,y_n)$. Here, $L$ is such that $y_i$ can be computed based only on $y_1,\ldots,y_{i-1}$ and $U$ is such that $x_i$ can be computed based only on $x_{i+1},\ldots,x_n$.

4. I should now try to describe the underlying information flow for a problem that can be solved by divide and conquer, but let's skip that step.

Let's look at differential equations for another example.

1. For an initial value problem of an ordinary differential equation, to flow of information goes from the past into the future, so it is relatively simple.

2. For a boundary value problem of an ordinary differential equation, the direction of the flow is no longer clear, but it is clear that the flow can be blocked/controlled by "some" values at the boundary of any interval. That's a bit similar to the situation where divide and conquer is applicable (which I omitted above).

Things get more challenging when the flow of information depends on the solution itself. This situation arises for some types of partial differential equations. The eikonal equation is one example of this, which is relatively easy to understand. A worse example are the equations for fluid flows, where the main flow of information will happen along the direction of the flow, but the flow itself is also a result of that information...

These examples may be a bit sketchy, and some important notions like well/ill-posed problems and inverse problems were completely omitted. But I hope that it has become clear what I mean by flow of information, and how it helps to judge the complexity of certain problems.