# Complexity Theory of <br>Total Functions <style> .reveal { font-size: 26px; } blockquote { width: 90% !important; } </style> --- ## Overview - Function Problems - Parity Argument - Pigeonhole Principle - Sink of DAG - Wrong Proof - Rogue Problems --- ## Function Problems - problems in which an output more elaborate than "yes" or "no" is sought - e.g. $\text{FSAT}$ is a function problem that asks an assignment if the given formula is satisfiable. - Also called search problem. ---- ## Function Problems - **FP**: the function problem version of **P** - **FNP**: the function problem version of **NP** - **TFNP**: the subclass of **FNP** that are guaranteed to have an answer - e.g. $\text{Nash}$, $\text{Minkowski}$, $\text{Necklace-Splitting}$, and $\text{Factoring}$ - **FP** $\subseteq$ **TFNP** $\subseteq$ **FNP** ---- ### **TFNP** - Any **TFNP** problem cannot be **FNP**-complete unless **NP** $=$ co-**NP** - Actually **TFNP** $=$ **F**(**NP** $\cap$ co-**NP**) - **TFNP** is a *semantic* class - *Semantic* classes seem to have no complete problems. - Are there important, syntactically definable, subclasses of **TFNP**? ---- #### Reductions in **TFNP** - *Karp* reductions in **TFNP**: We say a **TFNP** problem $\text{A}$ is polynomial-time many-one reducible to a **TFNP** problem $\text{B}$ if: 1. There exists a polynomial-time computable transformation $T$ from any instance $I_\text{A}$ of $A$ to an instance $T(I_\text{A})$ of $B$. 2. There exists a polynomial-time computable transformation $R$ from any solution $S$ of $T(I_\text{A})$ to a solution $R(S)$ of $I_{\text{A}}$. - *Cook* reductions in **TFNP**: We say a **TFNP** problem $\text{A}$ is polynomial-time *Turing* reducible to a **TFNP** problem $\text{B}$ if - There exists a polynomial-time oracle Turing machine that solves $A$, whenever all the oracle answers are solutions of $B$. - In **TFNP**, we are usually talking about *Karp* reductions. ---- ### **TNFP** ```graphviz digraph { node [shape = none, fontsize = 24] rankdir = BT size = 5 FP -> UEOPL UEOPL -> EOPL EOPL -> CLS FP -> PWPP CLS -> PLS CLS -> PPAD PPAD -> PPA PPAD -> PPADS PPADS -> PPP PWPP -> PPP PLS -> PTFNP PPA -> PTFNP PPP -> PTFNP PTFNP -> TFNP TFNP -> FNP {PLS PPA PPP rank=same} {PPAD PWPP rank=same} } ``` --- ## Parity Argument > All graphs of degree of two or less have an even number of leaves. ```graphviz graph { dim = 4 layout = neato node [shape = circle, label = ""] 1 -- 2 2 -- 3 3 -- 4 5 -- 6 6 -- 7 7 -- 5 8 -- 9 9 -- 10 } ``` ---- ### **PPA** - Polynomial Parity Argument > A search problem is in **PPA** if and only if it is reducible to **LEAF**. - **LEAF** - input: a circuit generated undirected graph with degree $\leq 2$ - A circuit having $n$ input bits and $2n$ output bits represents the two neighbors of the input node. - solution: any leaf $c \neq 0^n$, or $0^n$ if $0^n$ is not a leaf ---- ### Some Known **PPA**-complete Problems - $\text{Tucker}$ - Given a label function $\lambda : [m]^n \rightarrow [n] \times \{ -1, 1 \}$ that satisfies the condition of Tucker's lemma, find a complementary pair. - $\text{Borsuk–Ulam}$ - Given a continuous function $f : S^n \rightarrow \mathbb{R}^n$, find an $x$ with $\Vert f(x) - f(-x) \Vert \leq \epsilon$. - $\text{Consensus-Halving}$ - $\text{Necklace-Splitting}$ - Given an open nacklace with $ka_i$ beads of each color $i$, for $i \in [n]$, find the $(k - 1)n$ places to cut the necklace and the partition into $k$ subsets such that each subset contains precisely $a_i$ beads of each color $i$. - $\text{Discrete-Ham-Sandwich}$ - Given $n$ sets of points in $\mathbb{Z}^n$, find a hyperplane that splits each set into subsets of equal size. ---- ### **PPAD** - **PPA** for Directed Graph > A search problem is in **PPAD** if and only if it is reducible to **END-OF-LINE**. - **END-OF-LINE** - input: a circuit generated directed graph with in-degree, out-degree $\leq 1$ - A predecessor circuit with $n$ input bits and $n$ output bits represents the predecessor of the input node. - A successor circuit with $n$ input bits and $n$ output bits represents the successor of the input node. - solution: any source or sink $c \neq 0^n$, or $0^n$ if $0^n$ is not a source - **PPAD** $\subseteq$ **PPA** - Ignore the directions. ---- ### Some Known **PPAD**-complete Problems - $\text{Sperner}$ - Given a coloring function $f : [m]^n \rightarrow [n + 1]$ that satisfies the condition of Sperner's lemma, find a simplex (half of a hypercubelet) that consists of $n + 1$ colors. - $\text{Brouwer}$ - Given a continuous function $f : [0, 1]^n \rightarrow [0, 1]^n$, find a point $x$ such that $\Vert f(x) - x \Vert \leq \epsilon$ - $\text{Nash}$ - Given $n$ players each with a strategy set and a utility function, find an appoximate mixed strategy Nash equilibrium. - $\text{Hairy-Ball}$ - Given a continuous function $f : S^n \rightarrow S^n$, find a points $x$ such that $\Vert f(x) - x \Vert \leq \epsilon$. ---- ### **PPADS** - **PPAD** Restricted to Sink > A search problem is in **PPADS** if and only if it is reducible to **SINK**. - **SINK** - input: a circuit generated directed graph with in-degree, out-degree $\leq 1$ - A predecessor circuit with $n$ input bits and $n$ output bits represents the predecessor of the input node. - A successor circuit with $n$ input bits and $n$ output bits represents the successor of the input node. - solution: any sink, or $0^n$ if $0^n$ is not a source - **PPAD** $\subseteq$ **PPADS** - Ignore sources. - $\text{Positive-Sperner} \in$ **PPADS**-complete --- ## Pigeonhole Principle > If $n$ items are put into $m$ containers, with $n > m$, > then at least one container must contain more than one item. ---- ### **PPP** - Polynomial Pigeonhole Principle > A search problem is in **PPP** if and only if it is reducible to **PIGEON**. - **PIGEON** - input: a circuit $C$ with $n$ input bits and $n$ output bits - solution: $x \neq y \in \{ 0, 1 \}^n$ such that $C(x) = 0^n$ or $C(x) = C(y)$ - **PPAD** $\subseteq$ **PPADS** $\subseteq$ **PPP** - Treat the successor circuit as a pigeonhole circuit. ---- ### Some Known **PPP** Problems - $\text{Equal-Sums}$ - Given $n$ positive integers whose sum is less than $2^n - 1$, find two different subsets such that their sums are equal. - $\text{Minkowski}$ - Given a lattice $L$ with $det(L) < 1$, find a lattice point $x$ with $l_\infty$ norm less than $1$. - $\text{Dirichlet}$ - Given $n$ rational numbers $a_1, \dots, a_n$ and a positive integer $k$, find integers $p_1, \dots, p_n, q$ such that $\bigg| a_i - \cfrac{p_i}{q} \bigg| < \cfrac{1}{qk}$. - Complete: - $\text{Blichfeldt}$ - $\text{constrained-SIS}$ - a constrained version of the Short Integer Solution ---- ### **PWPP** - Polynomial Weak Pigeonhole Principle > A search problem is in **PWPP** if and only if it is reducible to **COLLISION**. - **COLLISION** - input: a circuit $C$ with $n$ input bits and $m$ output bits, where $m < n$ - solution: $x \neq y \in \{ 0, 1 \}^n$ such that $C(x) = C(y)$ - **PWPP** $\subseteq$ **PPP** - $\text{weak-cSIS} \in$ **PWPP**-complete --- ## Sink of DAG > Every DAG has at least a sink. ---- ### **PLS** - Polynomial Local Search > A search problem is in **PLS** if and only if it is reducible to **SINK-OF-DAG**. - **SINK-OF-DAG** - input: a circuit generated DAG with out-degree $\leq 1$. - a successor circuit $S$ with $n$ input bits and $n$ output bits represents the successor of the input node - a potential circuit $V$ with $n$ input bits and $m$ output bits represents the value of the input node - An edge exists if and only if the potential increase along the edge. - solution: a sink, or $0^n$ if $0^n$ has no successor ---- ### Some Known **PLS**-complete Problems - $\text{Max-Cut/Flip}$ - Find a maximal cut in respect to $\text{Flip}$. - $\text{Set-Cover/k-Change}$ - Find a maximal weighted set cover in respect to $\text{k-Change}$. - $\text{Metric-TSP/Lin-Kernighan}$ - Find a metric $\text{TSP}$ in respect to $\text{Lin-Kernighan}$. - $\text{Pure-Nash-Congestion}$ - Given a congestion game, find a pure strategy Nash equilibrium. ---- ### **CLS** - Continuous Local Search > A search problem is in **CLS** if and only if it is reducible to **3D-CONTINUOUS-LOCALOPT** - **3D-CONTINUOUS-LOCALOPT** - input: - $\epsilon > 0$ - a continuous function $V : [0, 1]^3 \rightarrow [0, 1]$ - a continuous function $N : [0, 1]^3 \rightarrow [0, 1]^3$ - solution: an approximate local optimum of $V$ with respect to $N$, i.e., $V(x) \leq V(N(x)) - \epsilon$ - **CLS** $=$ **PLS** $\cap$ **PPAD** - **UEOPL** $\subseteq$ **EOPL** $\subseteq$ **CLS** ---- ### Some Known **CLS**-complete Problems - $\text{KKT}$ - Given a non-empty bounded domain $D$, a continuous function $f$, and its gradient $\nabla f$, find an $\epsilon$-KKT point for the minimization problem of $f$ on domain $D$. - $\text{GD-Local-Search}$ - Given a non-empty bounded domain $D$, a continuous function $f$, and its gradient $\nabla f$, find a point $x$ where gradient descent for $f$ on domain $D$ with fixed step size $\eta$ terminates within $\epsilon$. - $\text{Banach}$ - $\text{Metametric-Contraction}$ - $\text{Nash-Congestion}$ - Given a congestion game, find an approximate mixed strategy Nash equilibrium. --- ## Wrong Proof > We have a consistent deductive system, and a concisely-represented proof having exponentially many steps, that leads to a contradiction. > There must be an error somewhere in the proof. ---- ### **PTFNP** - Provable **TFNP** > A search problem is in **PTFNP** if and only if it is reducible to **WRONG-PROOF** - **WRONG-PROOF** - input: a circuit generated proof consists two contradiction statements - solution: an incorrect line - **PPA**, **PPP**, **PLS** $\subseteq$ **PTFNP** ---- ### **TFNP** ```graphviz digraph { node [shape = none, fontsize = 24] rankdir = BT size = 5 FP -> UEOPL UEOPL -> EOPL EOPL -> CLS FP -> PWPP CLS -> PLS CLS -> PPAD PPAD -> PPA PPAD -> PPADS PPADS -> PPP PWPP -> PPP PLS -> PTFNP PPA -> PTFNP PPP -> PTFNP PTFNP -> TFNP TFNP -> FNP {PLS PPA PPP rank=same} {PPAD PWPP rank=same} } ``` --- ## Rogue Problems - These problems belong to **TFNP**, but are not yet classified to its subclasses. - $\text{Factoring}$ - $\text{Factoring}$ is reducible in randomized polynomial time to a **PPA** problem and a **PWPP** problem. - Both reductions can be derandomized under the assumption of the generalized Riemann hypothesis. - $\text{Ramsey}$ - Given a circuit generated graph with $4^n$ node, find $n$ nodes that are either a clique or an independent set. - A variation of $\text{Ramsey}$ called $\text{colorful-Ramsey}$ is **PWPP**-hard. - $\text{Bertrand-Chebyshev}$ - Find a prime between $n$ and $2n$. --- ## References - [On the complexity of the parity argument and other inefficient proofs of existence](https://www.sciencedirect.com/science/article/pii/S0022000005800637) - **PPA**, **PPAD**, **PPP** - $\text{Sperner}$, $\text{Brouwer}$, $\text{Equal-Sums}$ - [2-D Tucker is PPA complete](http://math.ucsd.edu/~jaisenbe/Research/Papers/TuckerPPA.pdf) - $\text{Tucker}$, $\text{Borsuk–Ulam}$ - [Consensus halving is PPA-complete](https://dl.acm.org/doi/abs/10.1145/3188745.3188880) - $\text{Consensus-Halving}$ - [The complexity of splitting necklaces and bisecting ham sandwiches](https://dl.acm.org/doi/abs/10.1145/3313276.3316334) - $\text{Necklace-Splitting}$, $\text{Discrete-Ham-Sandwich}$ - [The Complexity of Computing a Nash Equilibrium](https://epubs.siam.org/doi/abs/10.1137/070699652) - $\text{Nash}$ - [The Hairy Ball Problem is PPAD-Complete](https://arxiv.org/abs/1902.07657) - $\text{Hairy-Ball}$ - [The Relative Complexity of NP Search Problems](https://homes.cs.washington.edu/~beame/papers/NPSearchJournal.pdf) - **PPADS** - $\text{Positive-Sperner}$ ---- ## References - [Reductions in PPP](https://www.sciencedirect.com/science/article/pii/S0020019019300018) - $\text{Minkowski}, \text{Dirichlet}$ - [PPP-Completeness with Connections to Cryptography](https://arxiv.org/abs/1808.06407) - $\text{Blichfeldt}$, $\text{constrained-SIS}, \text{weak-cSIS}$ - [Integer factoring and modular square roots](https://www.sciencedirect.com/science/article/pii/S0022000015000768) - **PWPP**, $\text{Factoring}$ - [How easy is local search?](https://www.sciencedirect.com/science/article/pii/0022000088900463) - **PLS** - [Simple Local Search Problems that are Hard to Solve](https://epubs.siam.org/doi/10.1137/0220004) - $\text{Max-Cut/Flip}$ - [On the Complexity of Local Search for Weighted Standard Set Problems](https://link.springer.com/chapter/10.1007%2F978-3-642-13962-8_15) - $\text{Set-Cover/k-Change}$ - [On the complexity of local search](https://dl.acm.org/doi/10.1145/100216.100274) - $\text{Metric-TSP/Lin-Kernighan}$ - [The complexity of pure Nash equilibria](https://dl.acm.org/doi/abs/10.1145/1007352.1007445) - $\text{Pure-Nash-Congestion}$ ---- ## References - [Continuous Local Search](https://epubs.siam.org/doi/abs/10.1137/1.9781611973082.62) - **CLS** - [The Complexity of Gradient Descent: CLS = PPAD ∩ PLS](https://arxiv.org/abs/2011.01929) - **CLS** $=$ **PLS** $\cap$ **PPAD**, $\text{KKT}$, $\text{GD-Local-Search}$ - [Unique end of potential line](https://www.sciencedirect.com/science/article/pii/S0022000020300520) - **EOPL**, **UEOPL** - [A converse to Banach's fixed point theorem and its CLS-completeness](https://dl.acm.org/doi/10.1145/3188745.3188968) - $\text{Banach}$ - [CLS: New Problems and Completeness](https://arxiv.org/abs/1702.06017) - $\text{Metametric-Contraction}$ - [Settling the complexity of Nash equilibrium in congestion games](https://arxiv.org/abs/2012.04327) - $\text{Nash-Congestion}$ - [Towards a unified complexity theory of total functions](https://www.sciencedirect.com/science/article/pii/S0022000017302878) - **PTFNP**, $\text{Bertrand-Chebyshev}$ - [White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing](https://dl.acm.org/doi/abs/10.1145/3341106) - $\text{Ramsey}$, $\text{colorful-Ramsey}$