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.

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.

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 depth at most $d \leq \text{polylog}(n)$ :

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)$ at that index.
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.