Pigeonhole principle problem

• Input: A (polynomially computable) mapping f which maps a set of n + 1 items to a set of n items.
• Question: Find two items a and b such that f(a) = f(b).

Let x be a mapping, and y a 2-tuple of items in its domain. The binary relation in question P(x,y) has the meaning "the images of both entries of y under x are equal", which, since the mapping is polynomially computable, is polynomially decidable. Moreover, such tuple y must exist for any mapping because of the pigeonhole principle.

F(NP ∩ coNP)

The complexity class ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$ can be defined in two different ways, and those ways are not known to be equivalent. One way applies F to the machine model for ${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$. It is known that with this definition, ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$ coincides with TFNP.^[4] To see this, first notice that the inclusion ${\displaystyle {\mathsf {TFNP}}\subseteq {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$ follows easily from the definitions of the classes. All "yes" answers to problems in TFNP can be easily verified by definition, and since problems in TFNP are total, there are no "no" answers, so it is vacuously true that "no" answers can be easily verified. For the reverse inclusion, let R be a binary relation in ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$. Decompose R into ${\displaystyle R_{1}\cup R_{2}}$ such that ${\displaystyle (x,0y)\in R_{1}}$ precisely when ${\displaystyle (x,y)\in R}$ and y is a "yes" answer, and let R₂ be ${\displaystyle (x,1y)}$ such ${\displaystyle (x,y)\in R}$ and y is a "no" answer. Then the binary relation ${\displaystyle R_{1}\cup R_{2}}$ is in TFNP.

The other definition uses that ${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}}$ is known to be a well-behaved class of decision problems, and applies F to that class. With this definition, if ${\displaystyle {\mathsf {NP}}\cap {\mathsf {coNP}}={\mathsf {P}}}$ then ${\displaystyle {\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})={\mathsf {\color {Blue}FP}}}$.

Connection to NP

Intuition behind the lack of NP-hardness results for TFNP problems. The top image shows the typical form of a reduction that shows a problem is NP-hard. Yes instances map to yes instances and no instances map to no instances. The bottom image depicts the intuition for why it is difficult to show TFNP problems are NP-hard. TFNP problems always have a solution and so there is no simple place to map no instances of the original problem.

NP is one of the most widely studied complexity classes. The conjecture that there are intractable problems in NP is widely accepted and often used as the most basic hardness assumption. Therefore, it is only natural to ask how TFNP is related to NP. It is not difficult to see that solutions to problems in NP can imply solutions to problems in TFNP. However, there are no TFNP problems which are known to be NP-hard. Intuition for this fact comes from the fact that problems in TFNP are total. For a problem to be NP-hard, there must exist a reduction from some NP-complete problem to the problem of interest. A typical reduction from problem A to problem B is performed by creating and analyzing a map that sends "yes" instances of A to "yes" instances of B and "no" instances of A to "no" instances of B. However, TFNP problems are total, so there are no "no" instances for this type of reduction, causing common techniques to be difficult to apply. Beyond this rough intuition, there are several concrete results that suggest that it might be difficult or even impossible to prove NP-hardness for TFNP problems. For example, if any TFNP problem is NP-complete, then NP = coNP,^[3] which is generally conjectured to be false, but is still a major open problem in complexity theory. This lack of connections with NP is a major motivation behind the study of TFNP as its own independent class.

PLS

PLS (standing for "Polynomial Local Search") is a class of problems designed to model the process of searching for a local optimum for a function. In particular, it is the class of total function problems that are polynomial-time reducible to the following problem

Given input circuits S and C each with n input and output bits, find x such that ${\displaystyle C(S(x))\leq C(X)}$.

It contains the class CLS.

PPA

PPA (standing for "Polynomial time Parity Argument") is the class of problems whose solution is guaranteed by the handshaking lemma: any undirected graph with an odd degree vertex must have another odd degree vertex. It contains the subclass PPAD.

PPP

PPP (standing for "Polynomial time Pigeonhole Principle") is the class of problems whose solution is guaranteed by the Pigeonhole principle. More precisely, it is the class of problems that can be reduced in polynomial time to the Pigeon problem, defined as follows

Given circuit C with n input and output bits, find x such that ${\displaystyle C(x)=0}$ or x ≠ y such that ${\displaystyle C(x)=C(y)}$.

PPP contains the classes PPAD and PWPP. Notable problems in this class include the short integer solution problem.^[6]

PPAD

PPAD (standing for "Polynomial time Parity Argument, Directed") is a restriction of PPA to problems whose solutions are guaranteed by a directed version of the handshake lemma. It is often defined as the set of problems that are polynomial-time reducible to End-of-a-Line:

Given circuits S and P with n input and output bits ${\displaystyle S(0)\neq 0}$ and ${\displaystyle P(0)=0}$, find x such that ${\displaystyle P(S(x))\neq x}$ or ${\displaystyle x\neq 0}$ such that ${\displaystyle S(P(x))\neq x}$.

PPAD is in the intersection of PPA and PPP, and it contains CLS.

Here, the circuit S in the definition sends each point of the line to its successor, or to itself if the point is a sink. Likewise P sends each point of the line to its predecessor, or to itself if the point is a source. Points outside of all lines are identified by being fixed under both P and S (in other words, any isolated points are removed from the graph). Then the condition ${\displaystyle P(S(x))\neq x}$ defines the end of a line, which is either a sink or is such that S(x) = S(y) for some other point y; similarly the condition ${\displaystyle S(P(x))\neq x}$ defines the beginning of a line (since we assume that 0 is a source, we require the solution be nonzero in this case).

CLS

Continuous local search (CLS) is a class of search problems designed to model the process of finding a local optima of a continuous function over a continuous domain. It is defined as the class of problems that are polynomial-time reducible to the Continuous Localpoint problem:

Given two Lipschitz continuous functions S and C and parameters ε and λ, find an ε-approximate fixed point of S with respect to C or two points that violate the λ-continuity of C or S.

This class was first defined by Daskalakis and Papadimitriou in 2011.^[7] It is contained in the intersection of PPAD and PLS, and in 2020 it has been proven that ${\displaystyle {\mathsf {CLS}}={\mathsf {PPAD}}\cap {\mathsf {PLS}}}$.^[8][9] It was designed to be a class of relatively simple optimization problems that still contains many interesting problems that are believed to be hard.

Complete problems for CLS are for example finding an ε-KKT point,^[10] finding an ε-Banach fixed point^[11] and the Meta-Metric-Contraction problem.^[12]

EOPL and UEOPL

EOPL and UEOPL (which stands for "end of potential line" and "unique end of potential line") were introduced in 2020 by.^[10]

EOPL captures search problems that can be solved by local search, i.e. it is possible to jump from one candidate solution to the next one in polynomial time. A problem in EOPL can be interpreted as an exponentially large, directed, acyclic graph where each node is a candidate solution and has a cost (also called potential) which increases along the edges. The in- and out-degree of each node is at most one which means that the nodes form a collection of exponentially long lines. The end of each line is the node with highest cost on that line. EOPL contains all problems that can be reduced in polynomial time to the search problem End-of-Potential-Line:

Given input circuits S, P each with n input and output bits, and C with n input and m output bits, ${\displaystyle S(0)\neq 0}$, ${\displaystyle P(0)=0}$, and ${\displaystyle C(0)=0}$, find x such that

• x is the end of the line ${\displaystyle P(S(x))\neq x}$,
• x is the start of a second line ${\displaystyle S(P(x))\neq x\neq 0}$, or
• x violates the increasing cost ${\displaystyle P(S(x))=x}$, ${\displaystyle x\neq S(x)}$ and ${\displaystyle C(S(x))-C(x)\leq 0}$

Here, S sends each vertex of the graph to its successor, or to itself if the vertex is a sink. Likewise P sends each vertex of the graph to its predecessor, or to itself. Points outside the graph are identified by being fixed under both P and S. Then the first and second solution types are respectively the upper and lower ends of the line, and the third solution type is a violation of the condition that the potential increases along the edges. If this last condition is violated, the endpoint may not maximize the potential on the line. Therefore the problem is total: Either a solution is found or a short proof is found that the conditions are not satisfied.

UEOPL is defined very similarly, but it is promised that there is only one line. Hence finding the second type of solution above would violate the promise ensuring that the first type of solution is unique. A fourth solution type is added to provide another way of detecting the presence of a second line:

• two points x, y such that ${\displaystyle x\neq y,x\neq S(x),y\neq S(y)}$ and either ${\displaystyle C(x)=C(y)}$ or ${\displaystyle C(x)<C(y)<C(S(x))}$.

A solution of this type either indicates that x and y are on different lines, or indicates a violation of the condition that values on the same line are strictly increasing. The advantage of including this condition is that it may be easier to find x and y as required than to find the start of their lines, or an explicit violation of the increasing cost condition.

UEOPL contains, among others, the problem of solving the P-matrix-Linear complementarity problem,^[10] finding the sink of a Unique sink orientation in cubes,^[10] solving a simple stochastic game^[10] and the α-Ham Sandwich problem.^[13] Complete problems of UEOPL are Unique-End-of-Potential-Line, some variants of it with costs increasing exactly by 1 or an instance without the P circuit, and One-Permutation-Discrete-Contraction.^[10]

EOPL captures search problems like the ones in UEOPL with the relaxation that there are multiple lines allowed and it is searched for any end of a line. There are currently no problems known that are in EOPL but not in UEOPL.

EOPL is a subclass of CLS, it is unknown whether they are equal or not. UEOPL is trivially contained in EOPL.

FP

FP (complexity) (standing for "Function Polynomial") is the class of function problems that can be solved in deterministic polynomial time. ${\displaystyle {\mathsf {FP}}\subseteq {\mathsf {CLS}}}$, and it is conjectured that this inclusion is strict. This class represents the class of function problems that are believed to be computationally tractable (without randomization). If TFNP = FP, then ${\displaystyle {\mathsf {P}}={\mathsf {NP}}\cap {\mathsf {coNP}}}$, which should be intuitive given the fact that ${\displaystyle {\mathsf {TFNP}}={\mathsf {F}}({\mathsf {NP}}\cap {\mathsf {coNP}})}$. However, it is generally conjectured that ${\displaystyle {\mathsf {P}}\neq {\mathsf {NP}}\cap {\mathsf {coNP}}}$, and so TFNP ≠ FP.