TFNP Characterizations of Proof Systems and Monotone Circuits
summary
Paper proves necessary and sufficient conditions for when TFNP classes correspond to proof systems and to monotone-circuit models, and constructs a formal proof system from any TFNP class. Main positive claims: every TFNP has a proof-system and a circuit-model characterization. Converses hold precisely when a proof system is closed under decision-tree reductions and proves an efficiently verifiable reflection principle, and when a monotone model has a universal family of functions and is closed under low-depth reductions. Gives a TFNP class characterizing polynomial calculus.
AI-written summary · about
chapters (8)
- 0:00Start
- 0:33Monotone Circuit Complexity
- 1:37Interplay
- 4:16Characterizations by Total Search Problems
- 13:06TFNP: Interpolation & Lifting
- 14:02Our Results - Proof Complexity
- 17:09Our Results - Circuit Complexity
- 19:23Open Problem
related talks
30mSymbolic Execution of Hadamard-Toffoli Quantum Circuits
30mLower Bound Results for Hard Problems Related to Finite Automata
01h 32mInapproximability of Constraint Satisfaction Problems I
30mDeciding Reachability under Persistent x86-TSO
01h 31mCircuits of Bounded Depth
15mProgramming and Reasoning with Partial Observability
27mWhy Is A Math Proof Like A Unit Test?
19mA Formal Disproof of Hirsch Conjecture