TFNP

Last updated

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".

Contents

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]

Formal definition

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, [4] although TFNP problems and subclasses of TFNP had been defined and studied earlier. [5]

Examples

Pigeonhole principle problem

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.

Connections to other complexity classes

F(NP ∩ coNP)

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 .

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. Reductions to problems in NP and TFNP.svg
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.

Notable subclasses

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.

Diagram of inclusions between subclasses of TFNP. An arrow from class A to class B indicates A is a subset of B. All inclusions are believed to be strict, although none have been unconditionally proved to be strict. TFNP inclusions.svg
Diagram of inclusions between subclasses of TFNP. An arrow from class A to class B indicates A is a subset of B. All inclusions are believed to be strict, although none have been unconditionally proved to be strict.

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 .

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 or xy such that .

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 and , find x such that or such that .

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).

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 . [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, , , and , find x such that
  • x is the end of the line ,
  • x is the start of a second line , or
  • x violates the increasing cost , and
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 and either or .

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. , 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.

Related Research Articles

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.

<span class="mw-page-title-main">NP (complexity)</span> Complexity class used to classify decision problems

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.

<span class="mw-page-title-main">PSPACE</span> Set of decision problems

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.

<span class="mw-page-title-main">Interactive proof system</span>

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.

<span class="mw-page-title-main">Complexity class</span> Set of problems in computational complexity theory

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.

References

  1. Garg, Pandey, and Srinivasan. Revisiting Cryptographic Hardness of Finding a Nash Equilibrium. CRYPTO 2016.
  2. Habàcek and Yogev. Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds. SODA 2016.
  3. 1 2 Goldberg and Papadimitriou. Towards a Unified Complexity Theory of Total Functions. 2018.
  4. 1 2 Megiddo and Papadimitriou. A Note on Total Functions, Existence Theorems and Computational Complexity. Theoretical Computer Science 1989.
  5. Johnson, Papadimitriou, and Yannakakis. How Easy is Local Search?. Journal of Computer System Sciences, 1988.
  6. Sotiraki, Zampetakis, and Zidelis. PPP-Completeness with Connections to Cryptography. FOCS 2018
  7. Daskalakis and Papadimitriou. Continuous Local Search. SODA 2011.
  8. Fearnley, John; Goldberg, Paul W.; Hollender, Alexandros; Savani, Rahul (11 November 2020). "The Complexity of Gradient Descent: CLS = PPAD ∩ PLS". arXiv: 2011.01929 [cs.CC].
  9. Thieme, Nick (2021-08-17). "Computer Scientists Discover Limits of Major Research Algorithm". Quanta Magazine. Retrieved 2021-08-17.
  10. 1 2 3 4 5 6 Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul (December 2020). "Unique end of potential line". Journal of Computer and System Sciences. 114: 1–35. arXiv: 1811.03841 . doi:10.1016/j.jcss.2020.05.007. S2CID   220277586.
  11. Daskalakis, Constantinos; Tzamos, Christos; Zampetakis, Manolis (13 February 2018). "A Converse to Banach's Fixed Point Theorem and its CLS Completeness". arXiv: 1702.07339 [cs.CC].
  12. Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul (7 April 2017). "CLS: New Problems and Completeness". arXiv: 1702.06017 [cs.CC].
  13. Chiu, Man-Kwun; Choudhary, Aruni; Mulzer, Wolfgang (20 March 2020). "Computational Complexity of the α-Ham-Sandwich Problem". arXiv: 2003.09266 [cs.CG].