logo
ProjectForthcoming

Meta-Computational Perspectives on Proof Complexity

Location: Sweden

Source: EU Funding & Tenders Portal

Computational complexity theory seeks to understand the inherent difficulty of computational problems. For example, what is the fastest algorithm for factoring? Despite decades of progress, there are still problems—such as factoring—for which we lack efficient algorithms, and yet we cannot prove that they are intrinsically hard. Still, the assumption that factoring is indeed hard underpins much of

Status
Prospective
Location
Sweden
Updated
19 Nov 2026
Source
EU Funding & Tenders Portal

ConstructChat

Ask ConstructChat about Meta-Computational Perspectives on Proof Complexity

Pick a question to edit it, or write your own.

First answer free · no account

I am a

Project Information FAQ

Project Information

3 Q
The project “Meta-Computational Perspectives on Proof Complexity” is an infrastructure initiative, located in Sweden. Taiyo aggregates data on it from EU Funding & Tenders Portal.

Participants

Not available for this record.

Status

Original status

forthcoming

Taiyo status

Prospective

Taiyo last update

2026-11-19

Contact

Not available for this record.

Description

Description

Computational complexity theory seeks to understand the inherent difficulty of computational problems. For example, what is the fastest algorithm for factoring? Despite decades of progress, there are still problems—such as factoring—for which we lack efficient algorithms, and yet we cannot prove that they are intrinsically hard. Still, the assumption that factoring is indeed hard underpins much of modern cryptography and e-commerce. This raises a fundamental question: Why are we unable to determine the resources required to solve many computational problems? This project addresses such meta-complexity questions—questions about the complexity of computational problems themselves—within the field of proof complexity. While similar questions in circuit complexity have led to major breakthroughs over the past decade, their counterparts in proof complexity remain largely unexplored. I propose a systematic study of meta-complexity problems in proof complexity, with the overarching goal of explaining why current techniques fail to prove lower bounds for many natural formulas—even in weak proof systems. I aim to map the landscape of known lower bound methods, classify them by the complexity of their proofs of correctness, and push them to their theoretical limits. I also introduce two novel meta-complexity problems: encoding-independent lower bounds and the Minimum Proof Size Problem, both of which address notable gaps in the current literature. By pursuing these goals, I seek to identify fundamental barriers and to guide future research in the field. Moreover, just as the study of the Minimum Circuit Size Problem has revealed deep connections to cryptography, learning theory, and derandomisation, a systematic investigation of analogous questions in proof complexity may uncover similar links to other areas. Ultimately, this project contributes to the broader aim of understanding the limits of efficient computation and efficient reasoning.

Location

Country

Sweden

Source

Source

EU Funding & Tenders Portal

URL

More Details

Record type

Project

Article published date

2026-10-15

More on this project

Research

Free account

View all details

You are reading the public part. A free account opens the rest:

  • Every detail on this project
  • News and media coverage
  • Technical research
View all details

Free account · no card · lands you back on this project