Logical approaches to barriers in computing and complexity

Computability theory and complexity theory have their origins in logic. Famous names such as Gödel, Turing, Cook, and Kolmogorov connect these areas of computer science to foundations of mathematics. The fundamental goal of this area is to understand the limits of computability (that is analysing which problems can be solved on nowadays and future computers in principle) and efficient computability (that is understanding the class of problems which can be solved quickly and with restricted resources) where the most famous open problem is the P = NP-problem, listed on top of the collection of seven Clay Prize problems. Logic provides a multifarious toolbox of techniques to analyse questions like this, some of which promise to provide deep insights in the structure of limit of computation.
In our workshop, we shall focus on the following aspects: logical descriptions of complexity (e.g., descriptive complexity, bounded arithmetic), complexity classes of abstract, algebraic and infinite structures, barriers in proving complexity results, and Kolmogorov complexity and randomness. Descriptive complexity and bounded arithmetic are two complementary approaches to describe computational complexity in logical terms. The former is focussed on decision problems, while the latter is more concerned with search problems. Both environments render questions about complexity classes in a natural way, leading to important open problems in their areas (e.g. finding logics to capture certain complexity classes, or the separation problem for bounded arithmetic).