Overview
A computational search problem is called total if every input is guaranteed to admit at least one solution. Some examples:
- Given an integer $N > 1$, find a prime factor of $N$.
- Given a graph with $n$ vertices, find a clique or independent set of size at least $\log n / 2$.
- Given a simple graph with $n \geq 3$ vertices where every vertex has degree $\geq n/2$, find a Hamiltonian cycle.
As we can see, totality is often guaranteed by combinatorial lemmas. In this case, we used the Fundamental Theorem of Arithmetic, Ramsey's Theorem, and Dirac's Theorem.
Among total search problems, those whose solutions are efficiently verifiable form an important complexity class called TFNP (total-function NP). 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. Let $A \in \textsf{TFNP}^{dt}$ be a search problem taking inputs of size $n$. If $A$ reduces to $\textsf{Sink-of-DAG}_N$ in depth $d$, then $A$ reduces to $\textsf{Sink-of-DAG}_m$ in depth $O(d)$, where $m = n^{O(d)}$.
Key Insight
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.
This research was supported by NSERC Undergraduate Student Research Awards.