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:
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\).
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.
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
{"metaMigratedAt":"2023-06-15T19:01:49.496Z","metaMigratedFrom":"Content","title":"Complexity Theory of <br>Total Functions","breaks":true,"contributors":"[{\"id\":\"f9547eff-9cf4-46a1-8726-bc20b1554d01\",\"add\":16732,\"del\":2006}]"}