METACOMP Meta-complexity: A Unified Approach to the Complexity of Proofs and Computation
- Coordinator
- The Chancellor, Masters and Scholars of the University of Oxford, United Kingdom
- Runs
- 1 January 2026 to 31 December 2030
- Status
- Running
- EU funding
- €2.5m
- Total cost
- —
- Partners
- 1 organisations in 1 countries
- Type
- European Research Council grant
- Grant agreement
- 101201339
What the project is doing
In the project's own words, from its summary on CORDIS.
One of the most fundamental questions in computer science is the P vs NP question, which asks if every computational problem with efficiently verifiable solutions is efficiently solvable. Equivalently, it asks if all propositional tautologies have proofs that can be found efficiently. The answer is widely believed to be negative, but we lack a rigorous justification for this belief. The field of computational complexity approaches P vs NP and related questions by showing lower bounds (i.e., impossibility results) on efficient computations, while the field of proof complexity approaches these questions by showing lower bounds on efficient proofs for propositional tautologies.
Despite much effort, the best known lower bounds in both computational complexity and proof complexity are quite far from resolving the P vs NP question, and there are significant barriers to the success of known techniques. In this project, we will approach fundamental lower bound questions in computational complexity and proof complexity using the recently developed conceptual framework of ""meta-complexity"". Meta-complexity studies the complexity of computational problems and propositional statements that are themselves about complexity, eg., the Minimum Circuit Size Problem, which asks if a given Boolean function has small Boolean circuits.
Concepts and techniques from meta-complexity have been instrumental in major recent advances in theoretical cryptography and average-case complexity, overcoming known barriers. We will extend this methodology to attack some of the deepest questions in theoretical computer science, by showing new lower bounds on both proofs and computation, establishing strong connections between computational complexity and proof complexity, and giving applications to explicit constructions, learning and hardness of approximation.
A key aspect of our approach is that meta-complexity is a unifying framework, which applies equally well to proofs and computation.""
Topics
Who is involved
| Organisation | City | Country | Role |
|---|---|---|---|
| The Chancellor, Masters and Scholars of the University of Oxford | Oxford | United Kingdom | Coordinator |
Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI