Towards P≠NP from Extended Frege Lower Bounds

on YouTube ↗57m

" summary

If (a) S^1_2 proves a concrete E-function is hard to approximate by subexponential circuits and (b) S^1_2 proves a p-time reduction turns circuits breaking OWFs into learners, then failure of Extended Frege to p‑prove lower bounds for an explicit sequence f_n implies P≠NP; variants replace those hypotheses by existence of anticheckers, p-time witnesses against every p‑size SAT circuit, or an OWF from NP∉P/poly plus hardness of E. The argument uses bounded arithmetic, anti‑checker sets (Little‑Young minmax), derandomization and approximate counting.

AI-written summary · about

" chapters (7)

1. 0:00Introduction
2. 15:37System
3. 19:27Extensions
4. 23:42Theorem
5. 39:35Classical Questions
6. 40:20Holy Grail
7. 45:15Formalization

" related talks

• 53mNew Lower Bounds and Derandomization for ACC, and a...Lijie Chen · Lower Bounds, Learning, and Average-Case Complexity
• 01h 17mInapproximability of Constraint Satisfaction Problems VJohan Håstad · Real Analysis Boot Camp 2013
• 51mAllender's Conjecture and its Impacts on Meta-ComplexityShuichi Hirahara · Lower Bounds, Learning, and Average-Case Complexity
• 49mHard Languages in NP ∩ coNP and NIZK Proofs from Unstructured HardnessAmit Sahai, Alexis Korb · Minimal Complexity Assumptions for Cryptography 2023
• 47mNew Approaches to Heuristic Pac-learning vs. PRFsAri Karchmer · Lower Bounds, Learning, and Average-Case Complexity
• 58mDichotomy Theorems for Counting Problems IIXi Chen · Counting Complexity and Phase Transitions Boot Camp
• 48mUnstructured Hardness to Average-Case RandomnessRoei Tell · Lower Bounds, Learning, and Average-Case Complexity
• 01h 30mInapproximability of Constraint Satisfaction Problems IIJohan Håstad · Real Analysis Boot Camp 2013