Back to search

University of Birmingham

Proof complexity of systems of branching programs

Abstract

dc:description.abstract

This work investigates the proof complexity of multiple systems about deterministic and non-deterministic branching programs (BPs and NBPs respectively). It is based on work by Buss, Das and Knop, where they defined the systems eLpNqDT reasoning with (N)BPs by using extension variables/axioms to represent the dag-structure, over a language of (non-deterministic) decision trees. We start by focusing on positive branching programs (PBPs) i.e. NBPs where, for any 0-transition between two nodes, there is also a 1-transition. PBPs compute mono-tone Boolean functions, much like negation-free circuits or formulas do, but constitute a positive version of (non- uniform) NL, rather than P or NC1, respectively. We introduce eLNDT`, the positive fragment of eLNDT, that reasons about PBPs by considering restrictions on the form of inference rules we consider. The main result is that eLNDT` polynomially simulates eLNDT over positive sequents. Our proof method is inspired by a similar result for MLK (␣-free LK) and LK by Atserias, Galesi and Pudl´ak. 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 proofs of thepropositional pigeonhole principle. Our second contribution aims at defining Prover-Adversary games bespoke to the setting of branching programs. It builds upon work by Pudl´ak and Buss who defined a game with Boolean formulas as queries that corresponds to Hilbert-Frege/LK i.e. the canonical systems for reasoning about Boolean formulas. We adopt their definition to fit in our setting and provide games that correspond to eLDT and eLNDT. While the deterministic case is simple enough, the non-deterministic one requires simulating negations of NBPs for which, through a series of technical results, we formalize a (partial) non-uniform version of the Immerman-Szelepcs´enyi Theorem: NL “ coNL. The last part of this thesis presents the system o-eLDT, a specifically designed fragment of eLDT that reasons about ordered BPs (OBDDs).These are BPs whose paths only exhibit variables under a fixed order. Due to their ‘restricted’ nature, they posses multiple nice properties, for example, easy checking for equivalence between OBDDs. They have recently received wide interest in the literature with their proof (complexity) theoretic analysis initiated by work from Atserias, Kolaitis and Vardi where they, among others, defined the system OBDDp^, wq. We finish by comparing the expressive strength of o-eLDT and OBDDp^, wq, concluding that the former polynomially simulates the latter.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Delkos, Avgerinos

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Delkos, Avgerinos. Proof complexity of systems of branching programs. d_ph thesis, University of Birmingham, 2024.