The Proof Analysis Problem for Constant-Depth Frege
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "The Proof Analysis Problem for Constant-Depth Frege".
Jane: Here's the gist of the paper. The paper presents a parallel algorithm for solving the Proof Analysis Problem (PAP) of Arteche, Atserias, de Rezende, and Khaniki (FOCS 2025), which asks to extract a satisfying assignment for a CNF formula phi given its Resolution lower bound proof Ref s(phi).
Tom: The primary contribution is an assignment extraction algorithm computable by polynomial-size TC 0 circuits and quasipolynomial-size AC 0 circuits, with the correctness of the latter proven within quasipolynomial-size AC 0-Frege.
Jane: This achievement stems from a novel formalization of the Atserias–Müller lower bound within the relativized theory T42(alpha) of bounded arithmetic, which corresponds to depth-4 Frege systems.
Tom: This new approach yields quasipolynomial-size AC 0-Frege proofs for a broad class of Resolution lower bounds, advancing Pudlák's question.
Paper summary: Tom: So to wrap up, we've seen this paper, "The Proof Analysis Problem for Constant-Depth Frege," and it really focuses on finding a way to extract satisfying assignments from proof size lower bounds in Resolution.
Jane: It’s about giving us an assignment extraction algorithm that works using polynomial size TC0 circuits or quasipolynomial size AC0 circuits >
Lu: The authors achieved this by formalizing the Atserias–Müller lower bound within the theory T42 alpha of bounded arithmetic which links it to depth-four Frege systems >
Meng: For practical terms, this means we have a method for extracting those assignments in low-depth circuit classes without needing impossibly large resources >
Lalam: The paper also shows that while they can solve the extraction problem efficiently for Resolution, the Proof Analysis Problem remains NP-hard under quasipolynomial time reductions for systems that p-simulate depth-two Frege > <ref:2611.08305#pg1>
Tom: It means there are still hard problems when you look at broader classes of logic or larger proof sizes, but we have better tools to navigate those specific lower bounds >
Jane: The authors proved that automating the search just on Resolution lower bounds is enough to automate proof systems over all formulas in quasipolynomial time if the system has a depth greater than or equal to three >
Lu: It's a lot of machinery, but they’re showing how these deep formalizations help us understand exactly where things fall on the complexity spectrum between what's easy and what's computationally intractable >
Conclusion: Tom: So we're wrapping up this talk on "The Proof Analysis Problem for Constant-Depth Frege." Basically, these authors showed that you can actually build an algorithm to find satisfying assignments from Resolution lower bounds using very efficient circuit sizes.
Jane: So, what does that mean for us? Like, if a proof system is shallow—constant depth—we have a better way to analyze its proofs without needing an impossibly big search space.
Lu: Exactly. They’ve done this by finding a new way to look at those lower bounds using bounded arithmetic, which is basically a formal math language for describing the universe. This lets them prove their extraction algorithm works with quasipolynomial size circuits in a setting that's deeper than what was possible before.
Meng: I'm interested in the practical side here. If this works for constant-depth systems, does it mean we can actually automate proof search for those kinds of logic systems on real data? What are the actual resource costs they’re talking about?
Lalam: The paper shows that automating the search just on these Resolution lower bounds is enough to automate proof systems over all formulas if their depth is three or more. This suggests that if you can efficiently find assignments for Resolution proofs, you can actually handle most other proof systems on all possible formulas with reasonable time.
Tom: It means we’re getting tighter constraints on what’s computationally hard in logic. The authors also highlighted that the basic way they used to approach Resolution lower bounds doesn't apply to constant-depth systems because there are NP-hard problems still lurking there.
Jane: So, while this is great for Resolution and bounded arithmetic, it also tells us where the real complexity lies when we move beyond those specific structures. It’s a map of what’s solvable versus what remains hard across different proof systems.
Lu: Right. The next thing we should look at is how these results connect to the broader landscape of proof systems and their limitations, especially when considering those NP-hard cases they mentioned for constant-depth Frege itself.
Noel Arteche, Susanna F. de Rezende, Erfan Khaniki, Kilian Risse
Lund University · University of Copenhagen · University of Oxford · ETH Zürich
cs.CC
Submitted: 2026-11-05
Updated: 2026-11-05
Comments: An extended abstract of this paper will appear at the 67th IEEE Symposium on Foundations of Computer Science (FOCS 2026)
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 100/100
The gist: The paper presents a parallel algorithm for solving the Proof Analysis Problem (PAP) of Arteche, Atserias, de Rezende, and Khaniki (FOCS 2025)…
Key concepts
- Proof Analysis Problem (PAP)
- This is the task of finding a satisfying assignment for a given CNF formula by analyzing its Resolution lower bound proof. Essentially, it asks: can we efficiently extract an answer from the structure of a proof that shows a formula is unsatisfiable?
- Resolution Lower Bound Proof ($ ext{Ref}_s(\varphi)$)
- This is the specific type of proof used in this problem. It's a formal derivation showing that a CNF formula $\varphi$ cannot be satisfied, based on the Resolution rule. The length or structure of this proof is what the algorithm analyzes to extract an assignment.
- AC$^0$-Frege
- This refers to a specific class of propositional proof systems. AC$^0$ is a very restricted class of circuits (constant depth), and Frege systems are general proof systems. The paper proves that the assignment extraction can be done using quasipolynomial-size AC$^0$-Frege proofs, which relates the complexity of the problem to this system.
- Atserias–Müller Lower Bound
- This is a key concept formalized in bounded arithmetic theories (T42($\alpha$)). It provides a lower bound on the complexity or structure of Resolution proofs. The paper uses a new formalization of this bound to establish proof systems' hardness results.
Terminology
Summary
The paper presents a parallel algorithm for solving the Proof Analysis Problem (PAP) of Arteche, Atserias, de Rezende, and Khaniki (FOCS 2025), which asks to extract a satisfying assignment for a CNF formula phi given its Resolution lower bound proof Ref s(phi). p. 0 de Rezende‡ Erfan Khaniki§ Kilian Risse¶
Abstract
We give a parallel algorithm for the Proof Analysis Problem of Arteche, Atserias, de Rezende, and
Khaniki (FOCS 2025). The problem asks, given a CNF formula 𝜑 on 𝑛 variables and a proof 𝜋 of a size-𝑠
Resolution lower bound on 𝜑, encoded as ¬Ref𝑠 (𝜑), to extract a satisfying assignment for 𝜑 when one
exists. We devise a new algorithm that performs assignment extraction in
low-depth circuit classes. Specifically, we give an assignment extraction algorithm computable by polynomial-size TC0
circuits and by quasipolynomial-size AC0
circuits, and we prove the correctness of the latter within
quasipolynomial-size AC0
-Frege. Specifically, we give an assignment extraction algorithm computable by polynomial-size TC0
circuits and by quasipolynomial-size AC0
circuits, and we prove the correctness of the latter within
quasipolynomial-size AC0
-Frege. This is achieved thanks to a new formalization of the Atserias–Müller
lower bound in the relativized theory T
4
2
(𝛼) of bounded arithmetic, which corresponds to depth-4 Frege
systems. This yields quasipolynomial-size AC0
-Frege proofs for a broad class of Resolution lower bounds,
making progress on a question of Pudlák. A key feature of our approach is an improved parameter
regime: unlike prior AC0
-Frege formalizations of Resolution lower bounds by Li, Li, and Ren (STOC 2026),
which only proved ¬Ref𝑠 (𝜑) formulas for 𝑠 = 2
Ω(𝑛)
, our approach applies to all 𝑠, including 𝑠 = 𝑛
𝑂 (1)
. A key feature of our approach is an improved parameter
regime: unlike prior AC0
-Frege formalizations of Resolution lower bounds by Li, Li, and Ren (STOC 2026),
which only proved ¬Ref𝑠 (𝜑) formulas for 𝑠 = 2
Ω(𝑛)
, our approach applies to all 𝑠, including 𝑠 = 𝑛
𝑂 (1)
. With these improved parameters we show that the Proof Analysis Problem for AC0
-Frege is NP-hard
under quasipolynomial-time reductions, which rules out certain Atserias–Müller-type approaches to
the hardness of automating constant-depth Frege. With these improved parameters we show that the Proof Analysis Problem for AC0
-Frege is NP-hard
under quasipolynomial-time reductions, which rules out certain Atserias–Müller-type approaches to
the hardness of automating constant-depth Frege. Furthermore, automating AC0
-Frege on Resolution
lower bound formulas suffices to automate it on all formulas.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The paper establishes several related results concerning Resolution and proof systems:
-
Resolution Assignment Extraction: Theorem 1.1 states that the assignment extraction problem for Resolution is computable by uniform multi-output TC 0 circuits of polynomial size, and Theorem 1. p. 4
2 shows it is computable by uniform multi-output AC 0 circuits of quasipolynomial size. p. 4Where the paper says it
1 (Assignment extraction in TC0 , informal). The assignment extraction problem for Resolution is computable by uniform multi-output TC0 circuits of polynomial size.
For s at least n squared, the search version (ExtractionRes) is solvable by P-uniform multi-output circuits of quasipolynomial size and constant depth (Theorem 3. p. 4Where the paper says it
2 (Assignment extraction in quasipolynomial AC0 , informal). The assignment extraction problem for Resolution is computable by uniform multi-output AC0 circuits of quasipolynomial size.
9), and ExtractionRes is FTC 0 when s at least n squared (Theorem 3. p. 2Where the paper says it
The assignment extraction problem for Resolution is computable by uniform multi-output TC0 circuits of polynomial size. This algorithm inspects each clause of the Resolution refutation in parallel in search for a satisfying assignment, and we show that there always exists a clause in the refutation that hides the assignment.
8).Where the paper says it
Due to the lower bound on Ref formulas, Resolution is readily seen to be analyzable: if the refutation of Ref𝑠 (𝜑) is short and correct, then it must be for a satisfiable 𝜑. It is not hard to see that for any system 𝑆 at least as strong as Resolution, if 𝑆 is analyzable, then the system cannot be automated unless P = NP, thereby generalizing the Atserias–Müller reduction.
-
NP-hardness Results: Theorem 8.5 demonstrates that for any propositional proof system S that p-simulates depth-2 Frege, the Proof Analysis Problem for S is NP-hard under quasipolynomial-time reductions, implying the basic Atserias–Müller approach for Resolution lower bounds does not apply to constant-depth systems. p. 5
The NP-hardness of PAP for constant-depth Frege is confirmed by Theorem 1. p. 5Where the paper says it
For every propositional proof system 𝑆 that p-simulates depth-2 Frege, it holds that the Proof Analysis Problem for 𝑆 is NP-hard under quasipolynomial-time reductions. This immediately implies that the basic Atserias–Müller approach of using the Ref formula for Resolution for hardness of automatability does not work for constant-depth systems.
6.Where the paper says it
6 (NP-hardness of PAP, informal). For every propositional proof system 𝑆 that p-simulates depth-2 Frege, it holds that the Proof Analysis Problem for 𝑆 is NP-hard under quasipolynomial-time reductions.
-
General Proof Systems: Theorem 8.4 establishes a general NP-hardness result for PAP concerning proof systems S 1 and S 2 related by polynomial blow-up, showing that the PAP problem is NP-hard under many-one reductions computable in time poly(t(n)). p. 5
Where the paper says it
6 (NP-hardness of PAP, informal). For every propositional proof system 𝑆 that p-simulates depth-2 Frege, it holds that the Proof Analysis Problem for 𝑆 is NP-hard under quasipolynomial-time reductions.
-
Automatability: Theorem 1.7 shows that for every d at least 3, the proof system PK d+1/2 is automatable on Ref formulas in quasipolynomial time if and only if it is automatable on all CNF formulas in quasipolynomial time, suggesting that efficient proof search over Resolution lower bounds is sufficient to automate proof systems over all formulas. p. 6
Where the paper says it
7 (Automatability in terms of Ref formulas, informal). For every 𝑑 ≥ 3, the proof system PK𝑑+1/2 is automatable on Ref formulas in quasipolynomial time if, and only if, it is automatable on all CNF formulas in quasipolynomial time.
The underlying technical machinery involves a new derandomization of the random restriction argument within APC 2(alpha) and the use of Jeřábek’s approximate counting framework to formalize the lower bound in T42(alpha). p. 0 This is achieved thanks to a new formalization of the Atserias–Müller
lower bound in the relativized theory T
4
2
(𝛼) of bounded arithmetic, which corresponds to depth-4 Frege
systems. One of the main technical ingredients in this formalization is a derandomization of the random
restriction argument of Atserias and Müller using limited independence and tools from unconditional
derandomization, combined with Jeřábek’s approximate counting framework. The idea in all of these results is to leverage the propositional translation as follows: if the system 𝑆 is
strong enough to prove the Atserias–Müller statement, then a size-ℓ proof of ¬𝜑 implies a quasipoly(ℓ)-size
proof of ¬Ref(Ref(𝜑)). We can now use the automating algorithm on this Ref formula to find a proof, and
finally, use the construction of Pudlák [Pud03] to recover a proof of ¬𝜑 from the proof of ¬Ref(Ref(𝜑)). 1 Construction of designs . 2 Bad restrictions from seeds .Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved assignment extraction for Resolution refutations can be performed by polynomial-size TC0 circuits, which allows for a more efficient parallel implementation than previous sequential approaches. This enables the extraction of a satisfying assignment for satisfiable CNF formulas in time poly(s).
-
The system can now perform assignment extraction in quasipolynomial-size AC0 circuits, which is achieved by carefully removing threshold gates from the TC0 algorithm using a quasipolynomial increase in size. This provides an improved parallel complexity class for this problem.
-
The proof of the Atserias–Müller lower bound can be formalized within the theory T 4/2 (alpha), which corresponds to depth-4 Frege systems, allowing for a new constructive proof using techniques from unconditional derandomization and Jeřábek’s approximate counting framework.
-
The Proof Analysis Problem for constant-depth Frege is shown to be NP-hard under quasipolynomial-time reductions, implying that the basic Atserias–Müller approach of using the Ref formula for hardness of automatability does not work for constant-depth systems.
-
A new extraction algorithm can extract a satisfying assignment for a CNF formula from a Resolution refutation in time poly(pi, s, n, m, l), where pi is the length of the refutation and l is related to n. This guarantees termination and correctness for satisfiable formulas under certain size constraints.
-
The search version of the Proof Analysis Problem for Resolution can be solved by QP-uniform multi-output circuits of quasipolynomial size and constant depth when s is at least n squared, moving the complexity from FZPP to FP.
Abstract
We give a parallel algorithm for the Proof Analysis Problem of Arteche, Atserias, de Rezende, and Khaniki (FOCS 2025). The problem asks, given a CNF formula φ on n variables and a proof π of a size- s Resolution lower bound on φ, encoded as Ref s(φ), to extract a satisfying assignment for φ when one exists. The original work gave a polynomial-time extraction algorithm for Resolution refutations that enabled a formalization of the Atserias-Müller lower bound (FOCS 2019) in Extended Frege, but it appeared inherently sequential. We devise a new algorithm that performs assignment extraction in low-depth circuit classes. Specifically, we give an assignment extraction algorithm computable by polynomial-size TC 0 circuits and by quasipolynomial-size AC 0 circuits, and we prove the correctness of the latter within quasipolynomial-size AC 0-Frege. This is thanks to a new formalization of the Atserias-Müller lower bound in the relativized theory 4 2(α) of bounded arithmetic, which corresponds to depth- 4 Frege systems. This yields quasipolynomial-size AC 0-Frege proofs for a broad class of Resolution lower bounds, making progress on a question of Pudlák. A key feature of our approach is an improved parameter regime where we get AC 0-Frege formalizations of Resolution lower bounds Ref s(φ) for all s, including s = n O(1). W also show that the Proof Analysis Problem for AC 0-Frege is NP-hard under quasipolynomial-time reductions, which rules out certain Atserias-Müller-type approaches to the hardness of automating constant-depth Frege. Furthermore, automating AC 0-Frege on Resolution lower bound formulas suffices to automate it on all formulas.
Sources
- The Proof Analysis Problem
- Proof complexity of CSP
- Feasibility of Primality in Bounded Arithmetic
- Parallelism and Adaptivity in Student-Teacher Witnessing
- Models of Bounded Arithmetic and variants of Pigeonhole Principle
- An independence of the MIN principle from the PHP principle
- Towards P$\ne$NP from Extended Frege lower bounds
Related papers
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?
- Interactive Proofs of Proximity for Model Evaluation