Anupam Das ; Avgerinos Delkos - Proof complexity of positive branching programs

lmcs:13874 - Logical Methods in Computer Science, March 11, 2025, Volume 21, Issue 1 - https://doi.org/10.46298/lmcs-21(1:23)2025
Proof complexity of positive branching programsArticle

Authors: Anupam Das ; Avgerinos Delkos

    We investigate the proof complexity of systems based on positive branching programs, i.e. non-deterministic branching programs (NBPs) where, for any 0-transition between two nodes, there is also a 1-transition. Positive NBPs compute monotone Boolean functions, just like negation-free circuits or formulas, but constitute a positive version of (non-uniform) NL, rather than P or NC1, respectively. The proof complexity of NBPs was investigated in previous work by Buss, Das and Knop, using extension variables to represent the dag-structure, over a language of (non-deterministic) decision trees, yielding the system eLNDT. Our system eLNDT+ is obtained by restricting their systems to a positive syntax, similarly to how the 'monotone sequent calculus' MLK is obtained from the usual sequent calculus LK by restricting to negation-free formulas. Our main result is that eLNDT+ polynomially simulates eLNDT over positive sequents. Our proof method is inspired by a similar result for MLK by Atserias, Galesi and Pudlák, that was recently improved to a bona fide polynomial simulation via works of Je\v{r}ábek and Buss, Kabanets, Kolokolova and Kouck\'y. Along the way we formalise several properties of counting functions within eLNDT+ by polynomial-size proofs and, as a case study, give explicit polynomial-size poofs of the propositional pigeonhole principle.


    Volume: Volume 21, Issue 1
    Published on: March 11, 2025
    Accepted on: January 31, 2025
    Submitted on: July 4, 2024
    Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science,Mathematics - Logic

    Consultation statistics

    This page has been seen 383 times.
    This article's PDF has been downloaded 113 times.