🔢 mathematics

Prover-Adversary games for systems over (non-deterministic) branching programs

This paper introduces Pudlak-Buss style Prover-Adversary games to characterize proof systems for deterministic and non-deterministic branching programs, establishing polynomial equivalences between these games and the proof systems eLDT and eLNDT while deriving a proof complexity version of the Immerman-Szelepcsenyi theorem.

Original authors: Anupam Das, Avgerinos Delkos

Published 2026-02-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anupam Das, Avgerinos Delkos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Game of "20 Questions" vs. A Rulebook

Imagine you are trying to prove that a complex machine (like a computer program) will never crash, or that it will always produce a specific result.

In the world of computer science, there are two main ways to do this:

The Rulebook (Proof Systems): You write down a long, formal list of logical steps, like a math textbook, proving step-by-step why the machine works.
The Game (Prover-Adversary Games): You play a game against a tricky opponent. You ask questions about the machine, and the opponent answers "Yes" or "No." If you can force the opponent to say two things that contradict each other (like "The light is on" and "The light is off" at the same time), you win.

The Goal of this Paper:
The authors, Anupam Das and Avgerinos Delkos, wanted to show that for a specific type of computer program (called Branching Programs), these two methods are actually equally powerful. If you can win the game, you can write a short proof. If you can write a short proof, you can win the game.

They focused on two types of programs:

Deterministic (BP): A machine that follows a single, straight path. Like a train on a single track.
Non-Deterministic (NBP): A machine that can "guess" or take multiple paths at once. Like a person walking through a maze who can try every door simultaneously.

The Challenge: The "Negation" Problem

The easy part was the Deterministic machine (the train).
If you have a train track, it's easy to build a "reverse" track. If the train goes Left, the reverse goes Right. The authors showed that for these simple machines, the Game and the Rulebook are perfectly matched.

The hard part was the Non-Deterministic machine (the maze).
In the maze, the machine can take many paths. To prove something is false in a maze, you have to prove that none of the paths lead to the exit.

The Problem: How do you build a "reverse" maze that proves "No path leads to the exit" without getting lost in an infinite loop?
The Analogy: Imagine you are trying to prove that a specific door in a giant, shifting maze is locked. To do this, you have to check every single path leading to it. If the maze is huge, checking every path one by one takes forever.

The Breakthrough: The "Magic Counter" (Immerman-Szelepcsényi)

The authors solved this hard problem by using a famous mathematical idea called the Immerman-Szelepcsényi Theorem.

The Metaphor: The "Exact Count" Trick
Imagine you are in a room with 1,000 people, and you need to know if exactly 50 of them are wearing red hats.

The Old Way: You ask everyone, "Are you wearing red?" and count. If you get the count wrong, you have to start over.
The Authors' Way: They realized you don't need to know who is wearing red. You just need a magical "Counter" that says, "I have counted 50 red hats."
- If the counter says "50," and you find a red hat, the counter says "51" (which is wrong, so you know something is up).
- If the counter says "50," and you find no red hats, you know you are safe.

The authors created a "Partial Negation" tool. Instead of trying to reverse the whole maze at once, they built a tool that says: "If exactly K people in this group are telling the truth, then this specific path is blocked."

By doing this for every possible number of "truth-tellers" (0, 1, 2... up to N), they could cover all bases. They proved that even though the maze is complex, you can still write a short, efficient "Rulebook" (Proof) to describe it, provided you use this "Magic Counter" trick.

Why Does This Matter?

Simplifying Complexity: It turns a messy, confusing game into a clean, logical proof. It shows that "guessing" (non-determinism) isn't as scary as we thought; we can still reason about it efficiently.
The "Logspace" Connection: In computer science, there is a hierarchy of difficulty.
- L (Logspace): Easy problems (like sorting a list).
- NL (Non-deterministic Logspace): Harder problems (like solving a maze).
- The Result: The authors showed that a system designed for "Alternating" problems (where you have to guess and then check and guess again) is actually no harder than the standard "Non-deterministic" system.
- The Metaphor: It's like proving that a game where you have to guess a password, then guess a security question, then guess a PIN, is actually no harder than just guessing the password. The "hierarchy" collapses.

Summary in a Nutshell

The Setup: The authors created a game to test computer programs.
The Discovery: They proved that winning the game is exactly the same as writing a short proof.
The Hurdle: Proving things about "guessing" programs (mazes) is hard because you have to check every possibility.
The Solution: They used a clever "counting" trick (Immerman-Szelepcsényi) to simplify the "guessing" into a manageable list of numbers.
The Impact: This proves that complex logical systems are more efficient and interconnected than we previously thought, bridging the gap between "guessing" and "proving."

In short: They built a bridge between a game of "20 Questions" and a formal math proof, showing that even when the computer is "guessing," we can still keep track of the rules perfectly.

1. Problem Statement

The paper addresses the challenge of characterizing proof systems for complexity classes L (Logspace) and NL (Nondeterministic Logspace) using Prover-Adversary games, a framework introduced by Pudlák and Buss.

Context: Previous work by Buss, Das, and Knop introduced proof systems eLDT (for deterministic branching programs, BPs) and eLNDT (for non-deterministic branching programs, NBPs). These systems reason about formulas representing the dag-structure of branching programs using extension variables.
The Gap: While proof systems (DAG-like) and games (Tree-like) are often equivalent, establishing this equivalence for non-deterministic systems is difficult.
- In deterministic settings, the language is closed under Boolean combinations (including negation) via simple constructions.
- In non-deterministic settings, computing the negation of an NBP is non-trivial. It requires the Immerman-Szelepcsényi theorem ($coNL = NL$), which states that the complement of an NL language is in NL.
- Existing proof systems struggle to formalize this negation efficiently within the game-theoretic framework (where strategies must be logarithmic in depth relative to proof size).

The authors aim to define games ($DB$ and $NB$) that correspond polynomially to $eLDT$ and $eLNDT$, respectively, and to resolve the technical hurdle of negating NBPs within the proof system.

2. Methodology

The authors employ a multi-step methodology combining game theory, proof complexity, and structural complexity theory:

A. Defining Prover-Adversary Games

They introduce two games, DB (deterministic) and NB (non-deterministic), where:

Players: Prover (asks queries) vs. Adversary (assigns Boolean values).
Queries: The queries are Boolean combinations of formulas representing branching programs (e.g., $A \land \neg B$ ).
Winning Condition: Prover wins if the Adversary's assignments lead to a "simple contradiction" (e.g., $0 \to 1$ , or a decision contradiction like $ApB \to 1, p \to 0, A \to 0$ ).
Strategy: A winning strategy is a binary tree. The depth of the tree corresponds to the logarithm of the proof size.

B. Translating Proofs to Strategies

The authors prove that any proof in $eLDT$ or $eLNDT$ can be converted into a winning strategy in $DB$ or $NB$.

Mechanism: They use a divide-and-conquer approach on the proof tree. A sequent is treated as a single query. The strategy searches for the first "false" sequent in the proof.
Result: If a proof has size $N$ , there exists a winning strategy with $O(\log N)$ rounds.

C. Translating Strategies to Proofs (The Core Challenge)

The converse direction (Strategy $\to$ Proof) is the paper's main technical contribution.

Deterministic Case ( $DB \to eLDT$ ): Straightforward. Since deterministic branching programs are closed under negation ( $\neg(ApB) \iff \neg A p \neg B$ ), the game queries can be translated directly into proof rules.
Non-Deterministic Case ( $NB \to eLNDT$ ): This requires formalizing the negation of an NBP.
- Step 1: De Morgan Normal Form: Strategies are converted to a form where negations only apply to atomic branching programs (no negations inside complex Boolean structures).
- Step 2: Partial Negation via Counting: To negate an NBP $B$ within the proof system, the authors formalize a non-uniform version of the Immerman-Szelepcsényi theorem.
- The Construction: They introduce "k-deciders" ( $A B^k_i C$ ). These are new extension variables that compute the negation of a sub-program $B_i$ relative to a fixed number $k$ of true inputs among a set of programs.
- Counting Mechanism: They utilize "threshold programs" (from previous work) to count how many inputs are true. The proof system performs an induction over the number of true inputs ( $k$ ) to exhaust all possibilities, effectively simulating the global negation.

3. Key Contributions

Game Characterization of eLDT/eLNDT:
The paper establishes polynomial equivalence between the proof systems $eLDT/eLNDT$ and the newly defined games $DB/NB$. This provides a canonical "tree-like" characterization for proof systems over branching programs.
Formalization of Immerman-Szelepcsényi in Proof Complexity:
The authors provide a novel, non-uniform formalization of the $coNL = NL$ theorem within the $eLNDT$ proof system.
- Unlike standard algorithmic proofs, they construct partial negations (k-deciders) that work relative to a specific count of true inputs.
- They avoid encoding counting directly into the NBP structure; instead, they rely on the proof system's ability to induct over the number of true inputs.
Proof Complexity Analogue of coNL = NL:
Using the machinery developed, they prove that the system $eLNDT$ (reasoning over NBPs) polynomially simulates a system $eL\exists\forall DT$ reasoning over $\exists\forall$ -alternating branching programs (programs with one alternation of non-determinism).
- This is a proof-complexity version of the collapse of the Logspace Hierarchy to the first level ($NL$).

4. Key Results

Theorem 4.1: $eLNDT$ (or $eLDT$) proofs of size $N$ translate to $O(\log N)$ round winning strategies in $NB$ (or $DB$).
Theorem 6.1: $NB$ (or $DB$) strategies of size $N$ translate to $poly(N)$ size proofs in $eLNDT$ (or $eLDT$).
Theorem 5.7 (Formalized Immerman-Szelepcsényi): For any set of NBPs, there exist extension variables (k-deciders) and polynomial-size proofs in $eLNDT$ that correctly simulate the decision of an NBP relative to a fixed number of true inputs.
Theorem 7.3: $eLNDT$ polynomially simulates $eL\exists\forall DT$ . This demonstrates that the proof system for NL is powerful enough to handle the second level of the logspace hierarchy ( $\exists\forall$ -BPs).

5. Significance

Bridging Theory and Games: The work successfully bridges the gap between "dag-like" proof systems (standard in complexity) and "tree-like" game systems (standard in bounded arithmetic and interactive proofs). This is crucial for understanding the structural properties of proofs in $L$ and $NL$.
Handling Non-Determinism: It resolves a long-standing technical difficulty in proof complexity: how to handle negation in non-deterministic settings without blowing up proof size. The "k-decider" construction is a sophisticated tool that isolates the complexity of negation to the proof level rather than the program level.
Hierarchy Collapse: The result that $eLNDT$ simulates alternating branching programs provides a concrete, syntactic proof of the collapse $coNL = NL$ within the realm of propositional proof complexity, independent of Turing machine simulations.
Future Directions: The authors suggest that these games could be used to compare $eL(N)DT$ with other proof systems like OBDD-based systems and to investigate the bounded arithmetic strength of the Immerman-Szelepcsényi theorem.

In summary, this paper provides a rigorous game-theoretic foundation for proof systems over branching programs and offers a groundbreaking formalization of the Immerman-Szelepcsényi theorem, demonstrating that the complexity of negating non-deterministic programs can be managed efficiently within a proof system.