We present a simplified proof of Solovay-Calude-Coles theorem
stating that there is an enumerable undecidable set with the
following property: prefix
complexity of its initial segment of length n is bounded by prefix
complexity of n (up to an additive constant).

more >>>

We present a new framework for the study of search problems and their
definability in bounded arithmetic. We identify two notions of
complexity of search problems: verification complexity and
computational complexity. Notions of exact solvability and exact
reducibility are developed, and exact $\Sigma^b_i$-definability of
search problems in bounded arithmetic ... more >>>

We introduce the idea of pushdown automata with the ability to flip
its stack. By bounding the number of times the stack can be flipped
we obtain a hierarchy of language classes from the context free
languages to the recursively enumerable languages. We show that each
class in ... more >>>