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. [1] [2] 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. [3]
The class TFNP is formally defined as follows.
It was first defined by Megiddo and Papadimitriou in 1989, [4] although TFNP problems and subclasses of TFNP had been defined and studied earlier. [5]
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. [4] To see this, first notice that the inclusion 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 . Decompose R into such that precisely when and y is a "yes" answer, and let R2 be such and y is a "no" answer. Then the binary relation is in TFNP.
The other definition uses that is known to be a well-behaved class of decision problems, and applies F to that class. With this definition, if then .
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.
The structure of TFNP is often studied through the study of its subclasses. These subclasses are defined by the mathematical theorem by which solutions to the problems are guaranteed. One appeal of studying subclasses of TFNP is that although TFNP is believed not to have any complete problems, these subclasses are defined by a certain complete problem, making them easier to reason about.
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
It contains the class CLS.
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 (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
PPP contains the classes PPAD and PWPP. Notable problems in this class include the short integer solution problem. [6]
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:
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 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 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:
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 . [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 (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:
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:
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 (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 , which should be intuitive given the fact that . However, it is generally conjectured that , and so TFNP ≠ FP.
In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.
The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.
In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.
In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete.
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.
In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.
In computational complexity theory, DTIME is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm. It is one of the most well-studied complexity resources, because it corresponds so closely to an important real-world resource.
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem. For function problems, the output is not simply 'yes' or 'no'.
In computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time .
In complexity theory, the Karp–Lipton theorem states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then
In computational complexity theory, Polynomial Local Search (PLS) is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. The main characteristics of problems that lie in PLS are that the cost of a solution can be calculated in polynomial time and the neighborhood of a solution can be searched in polynomial time. Therefore it is possible to verify whether or not a solution is a local optimum in polynomial time. Furthermore, depending on the problem and the algorithm that is used for solving the problem, it might be faster to find a local optimum instead of a global optimum.
In computer science, PPAD is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument. The class attracted significant attention in the field of algorithmic game theory because it contains the problem of computing a Nash equilibrium: this problem was shown to be complete for PPAD by Daskalakis, Goldberg and Papadimitriou with at least 3 players and later extended by Chen and Deng to 2 players.
Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.
In computational complexity theory, the complexity class PPP is a subclass of TFNP. It is the class of search problems that can be shown to be total by an application of the pigeonhole principle. Christos Papadimitriou introduced it in the same paper that introduced PPAD and PPA. PPP contains both PPAD and PWPP as subclasses. These complexity classes are of particular interest in cryptography because they are strongly related to cryptographic primitives such as one-way permutations and collision-resistant hash functions.
In computational complexity theory, PPA is a complexity class, standing for "Polynomial Parity Argument". Introduced by Christos Papadimitriou in 1994, PPA is a subclass of TFNP. It is a class of search problems that can be shown to be total by an application of the handshaking lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are given a graph and an odd-degree vertex, and we are asked to find some other odd-degree vertex, then we are searching for something that is guaranteed to exist.
In algorithmic game theory, a succinct game or a succinctly representable game is a game which may be represented in a size much smaller than its normal form representation. Without placing constraints on player utilities, describing a game of players, each facing strategies, requires listing utility values. Even trivial algorithms are capable of finding a Nash equilibrium in a time polynomial in the length of such a large input. A succinct game is of polynomial type if in a game represented by a string of length n the number of players, as well as the number of strategies of each player, is bounded by a polynomial in n.