Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-160 | 24th October 2025 19:19

Intersection Theorems: A Potential Approach to Proof Complexity Lower Bounds

RSS-Feed




TR25-160
Authors: Yaroslav Alekseev, Nikita Gaevoy
Publication: 27th October 2025 15:27
Downloads: 36
Keywords: 


Abstract:

Recently, Göös et al. (2024) showed that Res ? uSA = RevRes in the following sense: if a formula $\varphi$ has refutations of size at most $s$ and width/degree at most $w$ in both Res and uSA, then there is a refutation for $\varphi$ of size at most $poly(s·2^w)$ in RevRes. Their proof relies on the TFNP characterization of the aforementioned proof systems.

In our work, we give a direct and simplified proof of this result, simultaneously achieving better bounds: we show that if for a formula $\varphi$ there are refutations of size at most $s$ in both Res and uSA, then there is a refutation of $\varphi$ of size at most $poly(s)$ in RevRes. This potentially allows us to "lift" size lower bounds from RevRes to Res for the formulas for which there are upper bounds in uSA. This kind of lifting was not possible before because of the exponential blow-up in size from the width.

Similarly, we improve the bounds in another intersection theorem from Göös et al. (2024) by giving a direct proof of Res ? uNS = RevResT.

Finally, we generalize those intersection theorems to some proof systems for which we currently do not have a TFNP characterization. For example, we show that Res($\oplus$) ? u-wRes($\oplus$) = RevRes($\oplus$), which effectively allows us to reduce the problem of proving Pigeonhole Principle lower bounds in Res($\oplus$) to proving Pigeonhole Principle lower bounds in RevRes($\oplus$), a potentially weaker proof system.



ISSN 1433-8092 | Imprint