How long would it take to solve a problem?

Given a problem, is it clear where to begin?

If not, then would it be clear after some thought?
How long would it be until the approach is clear?

Indeed, many problems are of this nature, where it is unclear where to begin.

Perhaps, the Riemman Hypothesis.
Perhaps, Fermat's last Theorem
Perhaps, the Poincare Conjecture.

...

However, what if the approach is clear?
If it is, please start to solve the problem.

How long would it take to solve the problem?

Are we able to estimate the time needed to solve the problem?

Perhaps. Perhaps not.

How long would it take to discover the next prime number?
Or perhaps the next pair of twin prime?
Or perhaps the next Mersenn prime?

It is not clear how we would analytically attach an estimate to these questions.
In fact, it is not even clear whether the aforementioned things actually exist.

If it doesn't exist, then are we able to say it would be impossible for us to find one, even given
infinite amount of time?
We can not attach an estimation on infinity.

...

Although this can not be done for many problems,
but for some, we can indeed estimate the time needed to solve the problem.

Then, how can we characterize these estimates?
If we can, perhaps we can improve our understanding on the problems at hand.

What will be the estimate be dependent upon?
perhaps the difficulty of the problem?
or the size?
or the actually nature of the problem?

...nature?

...

Perhaps one way to characterize the estimate can be based on the size of the problem.
Intuitively, a 'larger' problem would require more time in general.

Then, can we take the abstract notion of 'large'ness, and give a precise interpretation
for the estimates?
Perhaps we can.

We can describe the 'largeness' of the problem, by using a number.
The larger the number, the 'larger' the problem is.
Seems intuitive.

Then, perhaps we can give a meaningful estimate based on the this number.

Well, what would be the logical question to ask?

Perhaps,
How does the estimate change as this number changes?

It seems like we are trying to find a relationship between the 2 objects.
Perhaps we can try to use mathematical functions to give the precise relationship.

Then, which mathematical function would best describe the relationship?
Well, we first agreed that as the number gets large, our estimate should also get large.
How many functions have such behaviour?

Well, sinusoidal functions surely do not, since they tend to oscillate, and does not become large.
What about rational functions of polynomials?
Some of them do tend toward infinity with an asymtote, but then what happens beyond that point?
Surely we can require the size of the problem to be just a bit bigger,
in which case, how do we understand the behaviour of the estimate?

Fortunately, there are a whole range of functions that do have the properties we are looking for.

1. Polynomials
2. Exponential
3. Logarithm
4. Factorial
...

In all cases,
we would expect the function value to become large, as the size of the problem increases.

Well, this seems easy.
We have found 4 very well understood functions to characterize our problem.

However, they indeed behave very differently.
The 4 functions have distinctive ways to grow large as the size increases.
From slowest to fastest, we have
Logarithm -> Polynomial -> Exponential -> Factorial

Interesting.
By asking the naive question of estimating the time, we actually arrive naturally at a point where
the problems seems to be split into 4 categories, with comepletly different behaviour.

But, are the problems really fundamentally different from each other?
If so, does the 'nature' of the problem in itself decide the category of the problem?

Astounding.
Just be doing some simple time estimation, we have perhaps arrived at a position to say that
there are indeed 'harder' problems than others, since some problems do seem to take more time
to solve.

However, are we really at a position to claim such things?
Do we understand the problems well enough to categorize them?
We started the analysis to improve our understanding in the first place.

...

Perhaps we can.
Then, for some problems perhaps, we can estimate the time using one of the functions.

Perhaps polynomial for one problem
and exponential for another.

Then, the estimation of time it takes grows much faster for the exponential problem,
compared to the polynomial problem.

It would be nice if we can solve a problem in less time.
Then, should we prefer to solve a polynomial problem?

But wait.
How did we decide that the other problem has to be exponential?
Is it clear how we would attempt to assign such lables to problems?

Perhaps, we can argue that we have indeed found a way to actually solve the problem.
We can manually solve the problem, then correlate the time used, to a mathematical function.

This seems very logical.
However, are there only one way to solve the problem?
Perhaps not.

Then, is there some other way to solve the problem, that we are not aware of?
Seems very likely.
If there is, is it likely to have the same behaviour for the time needed?
If the problem has a true 'nature', then we would presume that it would be the same behaviour.
However, if it does not follow the same behaviour, then what?

Did we change the 'nature' of the problem by finding a better solution?
Surely not, right?
Then, what have we done?
Does it mean that we have came to a better understanding to the problem?

Then is there a true 'nature' to the problem that is distinct to itself?
If so, then how can we understand such things.
Perhaps, by finding better solutions.
Then, can we know for certain whether we have attained a best solution?

...

We could start with the BOGO sort algorithm, which would have an estimate of factorial.
Do we naively believe that the 'sorting' has a charateristic of having a time dependence of factorial?
Then, we may discover bubble sort.
Would we say that the problem actually has a time dependence of polynomial?
Then, if we were to discover merge sort,
would we say now it's actually logarithmic dependence?
What next?

If we can only verify the 'nature' of problems through solutions,
then our verification is solely based on our knowledge of the solution.
Perhaps, we do not know every possible solution.

Then, can we claim without proof that some problems indeed have different time dependence
compared to others?
Can we claim we understand the 'nature' of problems, simply based on our current knowledge?

Perhaps.