Logical Approaches to Barriers in
Computing and Complexity

Scientific Scope

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 current 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.)

Another path to gain more understanding of complexity classes is to study them in more general settings, e.g. on general algebraic structures or for computational models with infinite resources. Questions arising in this area are how complexity classes are rendered in them, and what their relationship is.

It is well known that any proof of P ≠ NP will have to overcome two barriers: relativization and natural proofs. To this has recently been added a third barrier, called algebraic relativization or algebrization. The idea is that, when we relativize some complexity class inclusion, we should give the simulating machine access not only to an oracle A, but also to a low-degree extension of A over a finite field or ring.

With this workshop we want to address current questions in all these areas and stimulate communication and research between them. In particular, we want to inform researcher in these related but separated areas about current approaches and ideas, to stimulate new approaches to current questions.

Some of these aspects are particularly timely: recently, research in these areas became more intense. Part of this is the new conference series CiE (run by the Association for Computability in Europe) whose range of interests includes those of our workshop, creating an important focus on the emerging topics of the field. We consider this workshop as a research-oriented follow-up to the CiE conferences, allowing researchers ample time for discussions and joint work.

 websites: Arnold Beckmann 2009-10-17