Compressibility of TFNP Reductions

Joint work with Nathan Acheampong
Supervised by Professor Robert Robere

Presented at UCORE Poster Session 2025, McGill University. You can find the poster here and our writeup of the result here.

Overview

A computational search problem is called total if every input is guaranteed to admit at least one solution. Some examples:

Given $k \geq 2$ , find one of its prime factors.
Given a graph on $n$ vertices, find a clique or independent set of size at least $\frac{1}{2}\log n$ .
Given a directed acyclic graph, find a sink (a node with out-degree 0).

Totality often follows from combinatorial lemmas; here we use the Fundamental Theorem of Arithmetic, Ramsey’s Theorem, and the Directed Handshaking Lemma. Among total search problems, those whose solutions are efficiently verifiable form an important complexity class called TFNP (total-function NP). As in familiar classes like NP, we have reductions between total search problems.

We work in the black-box, or query, model $\textsf{TFNP}^{dt}$ , where the model of computation is the decision tree. A solution is verified by shallow decision trees — those of depth $\text{polylog}(n)$ , where $n$ is the length of the string encoding the instance. Since $\textsf{TFNP}^{dt}$ is not believed to contain a complete problem, it is studied through subclasses defined by their complete problems; one such subclass is $\textsf{PLS}^{dt}$ , for which $\textsf{Sink-of-DAG}$ is complete.

Definition (Decision-tree reduction).

Given two TFNP problems $A_n$ and $B_m$ , we say $A_n$ decision-tree reduces to $B_m$ in depth $d$ if there are two families of decision trees of $\text{polylog}(n)$ depth $d$ :

Forward maps: For every index $i$ of the input string to $B_m$ , there is a tree $f_i$ which takes the input $x$ to $A_n$ and computes the bit $f_i(x)$ , which is the $i$ ‘th input bit to $B_m$ .
Backward maps: For every solution $o$ of $B_m$ , there is a tree $T_o$ transforming $o$ into a solution $T_o(x)$ of $A_n$ .

The complexity of the reduction is $\log m + d$ . We write $A_n \leq_d B_m$ .

A reduction is compressed if the target problem has size $m = n^{O(d)}$ , polynomial in the input size and depth. This is significant because it bounds the complexity of the reduction to $O(d \log n)$ .

Revolutionary advances in TFNP theory have stemmed from the recent discovery that every TFNP problem has a corresponding propositional proof system which can efficiently prove that it is total. This mapping allows us to answer questions about TFNP problems by studying their associated proof systems. In particular, trade-off results from propositional proof complexity imply interesting bounds on the complexity of various TFNP reductions. However, these existence results do not reveal the underlying structures that admit the compressibility of these reductions. To understand these hidden structures explicitly, we provide a direct proof of such a reduction bound for the total search problem of finding a sink in a directed acyclic graph.

Main Result

Theorem. Reductions to $\textsf{Sink-of-DAG}$ are compressed. That is, $A \leq_d \textsf{Sink-of-DAG}_N$ implies $A \leq_{O(d)} \textsf{Sink-of-DAG}_{n^{O(d)}}$ .

The proof relies on a compression argument: decision tree paths querying the same set of literals can be identified and rewired together. Since there are at most $\binom{n}{d} \cdot 2^d = n^{O(d)}$ non-identical paths of depth $d$ , this bounds the number of distinct outputs and yields the desired reduction. The full proof, routing through the intermediate $\textsf{Iteration}$ problem, is available here.

For a much more detailed treatment of this theory, see Robert’s paper Separations in Proof Complexity and TFNP. The link between propositional proof complexity and TFNP was first established by Buss, Fleming, and Impagliazzo in the seminal TFNP Characterizations of Proof Systems and Monotone Circuits.