MCT · Metacomputational Complexity Theory

Metacomputational Complexity Theory

Understanding the power of computation is one of the biggest challenges in science and society. Computational complexity theory has been dedicated to the investigation of this generic goal but central questions of the field such as the famous P versus NP problem remain notoriously elusive. It is still consistent with our knowledge that all problems of practical interest are solvable by extremely efficient algorithms. Complexity theory attempts to identify what makes a problem computationally hard by proving lower and upper bounds on the complexity of concrete computational models such as Boolean circuits or propositional proof systems. However, even after several decades of intense research, the progress on proving that there is an explicit computationally hard problem remains incremental. In fact, several barrier results, which are recognized as a serious obstacle towards the goal of proving strong complexity lower bounds, have been discovered. Nevertheless, the barrier results also revealed new structural properties of complexity lower bounds and connected them to a wide range of areas such as learning theory, cryptography and mathematical logic. The present project, Metacomputational Complexity Theory (MCT), continued the development of complexity lower bounds with emphasis on their structural properties. It investigated complexity-theoretic properties of problems which themself capture central problems in complexity theory, e.g. complexity of proving complexity lower bounds. The overall objectives of the project are divided into two groups. 1. Hardness magnification, exploring the limits and consequences of an emerging theory of hardness magnification which arouse from investigating meta-computational aspects of complexity lower bounds and received a lot of attention as a promising approach overcoming previously existing barriers for proving lower bounds. 2. Structural theory, strengthening and developing new connections between methods for proving complexity lower bounds and other central concepts of computer science such as efficient learning algorithms, cryptographic primitives and automatability of proof-search. The MCT project led to a substantial progress on addressing these objectives. In particular, the project provided a better understanding of the potential of hardness magnification by expanding consequences of hardness magnification in areas such as learning theory and proof complexity. Further, the project developed a more robust theory of natural proofs establishing stronger connections between complexity lower bounds, cryptographic pseudorandom generators and learning algorithms. As one of the highlights of the project a conditional equivalence between learning algorithms and automatability of proof-search was established in a meta-mathematical setting.

Data: CORDIS, © European Union