In Descriptive Complexity, there is a vast amount of literature on
decision problems, and their classes such as \textbf{P, NP, L and NL}. ~
However, research on the descriptive complexity of optimisation problems
has been limited. In a previous paper [Man], we characterised
the optimisation versions of \textbf{P} via expressions ... more >>>

We focus on the problem of computing an $\epsilon$-Nash equilibrium of a bimatrix game, when $\epsilon$ is an absolute constant.
We present a simple algorithm for computing a $\frac{3}{4}$-Nash equilibrium for any bimatrix game in strongly polynomial time and
we next show how to extend this algorithm so as to ... more >>>

A dimension extractor is an algorithm designed to increase the effective dimension -- i.e., the computational information density -- of an infinite sequence. A constructive dimension extractor is exhibited by showing that every sequence of positive constructive dimension is Turing equivalent to a sequence of constructive strong dimension arbitrarily ... more >>>