The Dongola Times

(Anachronistic) Dispatches from the Kingdom of Makuria.
09th of June, 2013

My Open Problems in Optimisation

I have these open problems in my thinking about optimisation:

E Pluribus, Unum
In logic, we have the recognition of axioms. (Generally, axioms are considered self-evident once they have been recognised.) This recognition is an optimisation, because it reduces infinite arbitrary rules into a few rules from which the infinitude of rules can be deduced. So that instead of memorising the multiplication table (as we did, when I was in school), you just memorise the axioms of Peano arithmetic, which are few. Instead of memorising every single mathematical expression, you can just learn NBG set theory and get it over with.
This process of reducing the observations of centuries into a single theory—a small set of axioms—also exists in optimisation, such that instead of O(n) work (memorising the infinite possibilities of this multiplied with that), you have the O(1) work (of memorising a finite set of axioms). Out of the many, one.
In logic, they call it the recognition of axioms. The mathematicians say these things are discovered, not invented; and I concur. It already happens in optimisation, of course; but what is it called in optimisation?

Corollaries
In logic, we have the recognition of corollaries. The field that basically just studies corollaries is category theory. It is with category theory that you can express the corollary that Lord Bertrand Russell discovered: the addition operation is a corollary of the set union. With category theory, you would say that sets and numbers are both monoids. Category theorists often look at groups of functors literally as corollaries (“natural transformations”); but I am asking about the recognition of them. This problem is solved every time a Futamura projection is implemented, every time there is code reuse; so I know that we do recognise these corollaries, but I do not know how that would be expressed formally.
This process of seeing a repetition and abstracting it out into a single category such that you develop results for the category, which can then be used on set union as well as on addition, also exists in optimisation. This is because optimisation is essentially a way of replacing a “slow” member of one category (linked list, for example) with another member of the same category (random-access array, in that case) to get the same results but with better space or time complexity.
In logic, it is the recognition of corollaries; but what is it called in optimisation?

“Recognition”
Now, the problem with all this is that I will have to formalise the word “recognition”. Already, we see that we cannot escape the centrality of mind in all this. Since it is taboo, however, we can let mind be implicit in this study and still formalise the “recognition”. But the implications are that, once formalised, we can now deploy it for common problems in optimisation. These are my open problems.