Communications of the ACM
The World of TFNP
The complexity class TFNP (Total Function Nondeterministic Polynomial) is the class of total function problems that can be solved in nondeterministic polynomial time.
Credit: WMarsh1/Wikimedia Commons
How hard is it to solve a problem when a solution is guaranteed?
This question is at the heart of a groundbreaking 1994 paper by Christos Papadimitriou. In that paper, Papadimitriou, now Donovan Family Professor of Computer Science at Columbia University in New York, created an innovative suite of complexity classes to analyze the hardness of problems for which an existence theorem guarantees a solution.
A 2006 proof that nailed down the complexity of finding Nash equilibria in games confirmed the power of Papadimitriou's classes, and also inspired a host of new results.
These new results arise from connections between the classes and fundamental proof principles in topology. "You're studying not just computation, but you're studying mathematical proof and the idea that one proof principle is more powerful than another," said Paul W. Goldberg, a professor of computer science at the University of Oxford, U.K.
What is more, these results connect directly to the biggest unsolved problem in computer science, that of P versus NP.
The World of TFNP
If it is easy to check a solution to a problem, is it also easy to find a solution? This is the essence of the P versus NP question. The overwhelming consensus is that certain problems, called complete for the class NP or simply NP-complete, are inherently hard. NP-complete problems are found across all of science and engineering; not one is known to be efficiently solvable.
A twist on the P versus NP question: Is it easy to produce a solution when you know there always is one? This is the basis for the class TFNP. Standing for "total function nondeterministic polynomial time," TFNP contains NP problems for which a solution always exists. A classic example is the problem of factoring integers.
The hardness of NP-complete problems derives from the possibility that a solution might not exist. That possibility is absent for TFNP problems, which implies that none of them is NP-complete. Some TFNP problems, like factoring, do seem very hard, but their hardness has a character different from that of NP-complete problems and requires a different approach.
Combinatorics at the Bottom Level
This is just what Papadimitriou's 1994 paper laid out. "This paper is seminal in all senses of this word," said Avi Wigderson, a professor in the School of Mathematics of the Institute for Advanced Study at Princeton University. "[Papadimitriou] creates homes for tons of natural computational problems that didn't fit into previous complexity classes."
The guarantee of a solution for a TFNP problem typically comes in the form of an existence theorem. When you follow the proofs of those theorems step by step, "there is hard math, hard math, hard math," said Papadimitriou. The "hard math" steps can be translated into polynomial-time algorithms. But then comes a different kind of step, "sometimes mathematically the easiest step, a trivial combinatorial argument." That step, based on a fundamental combinatorial principle, apparently cannot be carried out in polynomial time.
Among the combinatorial principles he found in the proofs was the pigeonhole principle, which captures the obvious fact that if n objects are distributed into n-1 boxes, one box will contain two objects. Another is the "parity argument" for graphs, which states that if a graph has one odd vertex (that is, a vertex with an odd number of incident edges), it must have another. An analogue of the parity argument pertains to directed graphs.
Papadimitriou organized TFNP problems into classes based on these combinatorial principles. One class he called PPP, which contains problems for which the theorem guaranteeing a solution rests on the pigeonhole principle. For the class called PPA, the theorems rest on the parity argument for graphs, and for the class PPAD, on the parity argument for directed graphs.
Finding Fixed Points and Equilibria
One of the existence theorems that arises in Papadimitriou's paper is the Brouwer fixed point theorem. One version of this theorem states that any continuous mapping of a disk to itself must have a fixed point. Think of rotating, shifting, or swirling the points on the disk, or flipping them across a diameter. As long as the movement is continuous, the theorem guarantees that at least one point will return to exactly where it was before the movement started.
The associated computational problem is: Find the fixed points. Because the proof of Brouwer's theorem ultimately rests on the parity argument for directed graphs, this problem is in PPAD. Papadimitriou's paper showed that it is actually PPAD-complete, meaning that any other problem in PPAD can be efficiently reduced to it. This counts as strong evidence that the problem of finding Brouwer fixed points is intractable.
John Nash proved his famous 1951 theorem, which established the existence of equilibria in games, by using the Brouwer fixed point theorem. Nash's theorem changed the face of modern economics. When all the many algorithms formulated to find Nash equilibria turned out to be exponential in the worst case, suspicions arose that the problem is intractable. Its complexity remained elusive until 2006, when Constantinos Daskalakis, Goldberg, and Papadimitriou used the notion of graphical games to prove the problem of finding Nash equilibria is PPAD-complete.
"The [Nash] problem is so important and elegant," Wigderson said. "Now we know its exact complexity, at least in the sense that it captures all PPAD problems." Nash is a natural problem not only because it arose outside of complexity theory, but also because of the simplicity of its input, which is just a set of players and matrices encoding their strategies. In contrast, the input for an instance of Brouwer requires an algorithm that carries out a calculation at every point of the space in question.
The Nash result stimulated new interest in the TFNP complexity classes. A search in the MathSciNet database shows that between 1994 and 2006, just four computer science papers were published that mention PPA or PPAD. Since 2006, the number is close to 100.
More Connections to Topology
Many of those post-2006 papers focused on PPAD problems, especially those related to economics. What about PPA?
One prominent example of a PPA problem is associated with a fundamental result in topology called the Borsuk-Ulam theorem. This theorem says that for any function on a sphere, there exist two antipodal points having equal value under the function. Conceptually, it tells us that at every moment, there are two antipodal points on the Earth having equal temperature and equal air pressure.
The computational problem is: Find those antipodal points. This problem is in PPA because the proof of the Borsuk-Ulam theorem rests on the parity argument for graphs. A 2015 paper by James Aisenberg, Maria Luisa Bonet, and Sam Buss showed that this problem is PPA-complete.
A bigger advance came three years later, when Goldberg, together with Aris Filos-Ratsikas, provided the first proof showing a natural, real-world problem is PPA-complete. The problem, known as consensus-halving, is guaranteed to have a solution by virtue of the Borsuk-Ulam theorem. This puts consensus-halving into PPA territory.
A fair-division problem, consensus-halving addresses situations in which a group of people have varying valuations of different parts of an object. Is it possible to divide the object into two halves so that all the people value the two halves equally? For example, two families might need to split a plot of land into two regions so that all members of both families put equal value on the two regions.
To show that consensus-halving is PPA-complete, Filos-Ratsikas and Goldberg make use of a topological object called the Möbius band (or strip). Take a strip of paper, give it one twist, glue the ends together, and you have a Möbius band. A Möbius band has only one side; without the twist it would be a cylinder, which has two sides.
This highlights a fundamental topological property called orientability. A cylinder is orientable because "which way is up" remains the same no matter where you travel on the surface. This does not hold for the Möbius band, which is unorientable.
The unorientability makes the Möbius band the correct model to represent the symmetry between the two halves in the consensus-halving problem. It also reflects the topology of PPA problems. "In the PPA world, everything is unoriented," Goldberg said. "In PPAD, everything is oriented."
In a 2018 paper, Filos-Ratsikas and Goldberg extended these results to a classic combinatorics problem known as "necklace-splitting," and to a basic result in topology called the Ham Sandwich Theorem. They showed both are PPA-complete. Also, Goldberg and Alexandros Hollender last year proved the PPAD-completeness of yet another fundamental topological result, the Hairy Ball Theorem.
Connections to Crypto
The proof principle underlying PPAD is more specialized than that underlying PPA. Therefore, PPA contains PPAD as a subclass. PPP also contains PPAD, but the relationship between PPA and PPP is unknown. The pigeonhole principle is the most general of the three principles, and PPP seems the most enigmatic of the three classes.
A 2015 paper by Emil Jerabek proved a randomized result about integer factoring. It says roughly that if one accepts a degree of probability that an algorithm for factoring might fail to produce a factorization, then the problem of factoring is in PPA and in PPP.
"This paper connects factoring, a problem in TFNP which is central for cryptography, to these classes," Daskalakis said. "If it were complete (actually one would need average-case hard) for any of them, this would provide a complexity theoretic justification for using it in crypto. When you do crypto, you would like the confidence that breaking your crypto would collapse complexity classes."
Connecting TFNP classes with cryptography is also a motivation of a 2018 paper by Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis, which shows that a problem related to lattice-based cryptography is PPP-complete.
Direct Link to P versus NP
That PPA contains PPAD as a subset is reflected in the topological existence theorems and in the proof principles on which the theorems are based. "The belief that PPAD is a proper subset of PPA corresponds to the belief that the proof principle [for PPAD] is strictly weaker," Goldberg said. "You can derive Brouwer from Borsuk-Ulam, but not the other way around."
Does this mean PPA and PPAD are really distinct? It's a high-stakes question. If one could show the two classes are different, one could immediately conclude that P is different from NP.
No one claims such a momentous result is on the horizon. Nevertheless, part of the mystique of this area is the direct connection between these classes and the biggest open problem driving theoretical computer science today. As Goldberg said, "To understand how the TFNP classes intrinsically relate to each other may be a way to understand P versus NP."
Allyn Jackson is a journalist specializing in science and mathematics, who is based in Germany.
No entries found