ERC Advanced Grant · 2024
Meta-complexity: A Unified Approach to the Complexity of Proofs and Computation
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…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.