Investigating problems in the complexity class TFNP

This project falls within the EPSRC Theoretical Computer Science research area, specifically
in the domain of computational complexity theory.

The complexity class TFNP (Total Function Nondeterministic Polynomial) contains all total problems in the class NP. A problem is total if it has a solution for every input. Thus, a problem is in TFNP if for every input, it has a solution, and given such a solution, it can be checked that it is correct in polynomial time. An example of a problem in TFNP is FACTORING: "given a non-prime integer, return one of its prime factors". Clearly, every non-prime integer has at least one prime factor and thus the problem is total. It lies in NP, because given a prime factor, we can check in polynomial time that it is indeed prime and a factor of the input integer. The motivation for studying the complexity of problems in
TFNP is mostly theoretical. However, for some problems, this is important beyond purely theoretical considerations, such as for FACTORING, because the assumption that it is hard
is used in cryptographic systems.

The class TFNP is particularly interesting, because it is by definition extremely general, while not being well understood yet. More specifically, it seems quite difficult to classify problems in TFNP as intractable, i.e. probably very hard to solve in reasonable time. Unlike NP, it is believed that TFNP does not have any TFNP-complete problems, i.e. problems in TFNP that are as hard as any other problem in TFNP. Furthermore, it is extremely likely that TFNP
does not contain any NP-complete problems either. Thus, the standard tools for classifying a problem as intractable are not available. As a result, recent research has focused on subclasses of TFNP that do have complete problems.
Those subclasses are PPP, PPA, PPAD, PPADS and PLS. It has been shown that each of those subclasses has complete problems and thus they are useful for determining the relative
hardness of problems. If a problem is shown to be complete for one of those subclasses, then this is evidence that it is significantly hard.

The aim of this research project is to investigate open problems concerning TFNP and its subclasses. In the remainder of this proposal, we mention a few of the main open problems in this topic. First of all, there are important problems that are in TFNP, but have not yet been classified with respect to its subclasses. One example is the FACTORING problem mentioned above. It has been shown that this problem lies in the subclasses PPP and PPA, but it remains to determine whether it also lies in PPAD. Other examples of TFNP problems awaiting classification are RAMSEY and BERTRAND-CHEBYSHEV. The problem RAMSEY, "given a graph on 4n nodes, find a clique or an independent set of size n", is total by Ramsey's theorem. The problem BERTRAND-CHEBYSHEV, "given n, find a prime between n and 2n", is total by the Bertrand-Chebyshev theorem.

Another direction of research is finding non-generic complete problems for subclasses of TFNP, in particular PPA and PPP. All complete problems known for those subclasses are generic, i.e. their input contains the description of a Turing machine or a circuit. There is also interest in a new subclass called CLS, that is contained in the intersection of PPAD and PLS. This class is interesting because it contains a lot of problems for which no polynomial algorithms have yet been found, despite intense effort. Thus, we would like to investigate whether one of those problems is complete for CLS, or if CLS is in fact contained in P. Finally, we are also interested in investigating the new class PTFNP, which is a very general subclass of TFNP that contains all other five subclasses. Specifically, we would like to look for alternative simpler characterisations of this class.