Reverse Mathematics of Complexity Lower Bounds, Part II - Hanlin Ren

This presentation delves into the intricate relationship between computational complexity, proof complexity, and reverse mathematics, focusing on the difficulty of proving fundamental logical principles like the Pigeonhole Principle within various proof systems. It clarifies the equivalence between reducibility and provability in theoretical computer science and proof complexity, and then explores the lower bounds for proving the Pigeonhole Principle using resolution, a standard proof system. The discussion aims to inform professionals in theoretical computer science, logic, and mathematics about the complexities of computational proof and the foundational questions addressed by reverse mathematics.

Clarifying Reducibility and Provability Equivalence

The discussion begins by addressing prior confusion regarding the equivalence of reducibility and provability in the context of Total Search Problems (TSPs) in NP. Two TSPs, P and Q, are defined as problems where for any input, a polynomial-time verifiable solution exists. The totality of these problems can be formally expressed using universal quantifiers and existential quantifiers, with implicit polynomial bounds on the witness (solution) variables.

The equivalence between P reducing to Q and the provability of certain statements about P and Q in a formal theory is explored. Specifically, it's shown that if there's a Turing reduction from P to Q, and a theory T (like PV, which formalizes polynomial-time reasoning) can prove the correctness of this reduction and the totality of Q, then T can also prove the totality of P. This direction leverages the witnessing theorems of formal theories. Conversely, if T can prove that P implies Q, this statement can be reformulated into a $\Sigma_1^0$ sentence (a sentence with one existential quantifier followed by universal quantifiers). The KPT (Kolmogorov-Uspensky-Kolmogorov) witnessing theorem states that if such a sentence is provable in T, then there exists a polynomial-time student-teacher algorithm that can find a witness. The teacher's role can be implemented using oracle calls to Q, thus demonstrating that provability implies reducibility.

The KPT witnessing theorem is illustrated with an informal example: proving that $\sqrt{2}^{\sqrt{2}}$ is irrational. The student proposes a guess (e.g., $\sqrt{2}^{\sqrt{2}}$), and the teacher either accepts or provides a counterexample. This interaction, guided by the underlying mathematical proof, allows the student to eventually find the correct result, with the teacher's counterexamples being analogous to oracle calls to a problem.