The Journey from NP to TFNP Hardness

### Pavel Hubáček Moni Naor Eylon Yogev

###
Abstract:

The class TFNP is the search analog of NP with the additional guarantee that any instance
has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses
that capture the computational complexity of important search problems from algorithmic game
theory, combinatorial optimization and computational topology. Thus, one of the main research
objectives in the context of TFNP is to search for efficient algorithms for its subclasses, and at
the same time proving hardness results where efficient algorithms cannot exist.

Currently, no problem in TFNP is known to be hard under assumptions such as NP hardness,
the existence of one-way functions, or even public-key cryptography. The only known hardness
results are based on less general assumptions such as the existence of collision-resistant hash functions,
one-way permutations less established cryptographic primitives (e.g., program obfuscation
or functional encryption).

Several works explained this status by showing various barriers to proving hardness of TFNP.
In particular, it has been shown that hardness of TFNP hardness cannot be based on worst-case
NP hardness, unless NP = coNP. Therefore, we ask the following question: What is the weakest
assumption sufficient for showing hardness in TFNP?

In this work, we answer this question and show that hard-on-average TFNP problems can be
based on the weak assumption that there exists a hard-on-average language in NP. In particular,
this includes the assumption of the existence of one-way functions. In terms of techniques, we
show an interesting interplay between problems in TFNP, derandomization techniques, and zero-knowledge
proofs.

Paper: PDF. Slides:
ppt.

##### Related On-Line
Papers:

- Ilan Komargodski, Moni Naor and Eylon Yogev,
*
White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing*,FOCS 2017,
Abstract , PDF .

Back to: On-Line Publications, Recent Papers

Back Home