Толық Функциялық Есептеулер Классы TFNP және PPAD

Complexity class
In computational complexity theory, the complexity class TFNP is the class of total function problems which can be solved in nondeterministic polynomial time. That is, it is the class of function problems that are guaranteed to have an answer, and this answer can be checked in polynomial time, or equivalently it is the subset of FNP where a solution is guaranteed to exist. The abbreviation TFNP stands for "Total Function Nondeterministic Polynomial". TFNP contains many natural problems that are of interest to computer scientists. These problems include integer factorization, finding a Nash Equilibrium of a game, and searching for local optima. TFNP is widely conjectured to contain problems that are computationally intractable, and several such problems have been shown to be hard under cryptographic assumptions. However, there are no known unconditional intractability results or results showing NP hardness of TFNP problems. TFNP is not believed to have any complete problems.

The class TFNP is formally defined as follows. A binary relation P(x,y) is in TFNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(x,y) holds given both x and y, and for every x, there exists a y which is at most polynomially longer than x such that P(x,y) holds. It was first defined by Megiddo and Papadimitriou in 1989, although TFNP problems and subclasses of TFNP had been defined and studied earlier.

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.

The complexity class 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 It is known that with this definition, coincides with TFNP.

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 1=S(0) \ne 0 and 1=P(0) = 0, find x such that 1=P(S(x)) \ne x or 1=x \ne 0 such that 1=S(P(x)) \ne 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 1=P(S(x)) \ne 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 1=S(P(x)) \ne x defines the beginning of a line (since we assume that 0 is a source, we require the solution be nonzero in this case).

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. It is contained in the intersection of PPAD and PLS, and in 2020 it has been proven that 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, finding an ε Banach fixed point and the Meta Metric Contraction problem.

EOPL and UEOPL (which stands for "end of potential line" and "unique end of potential line") were introduced in 2020 by. 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. 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 (complexity) (standing for "Function Polynomial") is the class of function problems that can be solved in deterministic polynomial time. , 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 1=\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP} , which should be intuitive given the fact that 1=\mathsf{TFNP} = \mathsf{F}(\mathsf{NP} \cap \mathsf{coNP}). However, it is generally conjectured that , and so TFNP ≠ FP.