Total function NP

The class of total search problems in FNP — search problems where a solution is guaranteed to exist for every input but may be hard to find. Formally, a problem is in TFNP if there is a polynomial-time verifier $V$ such that:

1. For every input $x$, there exists a witness $w$ with $V(x,w)=1$ (totality).
2. The witness $w$ has length polynomial in $|x|$.

Totality means the problem cannot be NP-complete (unless NP = coNP), since a reduction from SAT to a total problem yields NP certificates of unsatisfiability (Megiddo–Papadimitriou, TCS 1991). This makes TFNP a natural home for problems believed to be hard but not NP-hard.

See the complexity zoo entry here.

Subclasses

TFNP contains several important subclasses defined by the combinatorial principle guaranteeing existence of a solution:

• PPAD (Polynomial Parity Argument, Directed): finding a Nash equilibrium is PPAD-complete, already for two-player games — DGP09, CDT09. PPAD is hard assuming iO and one-way functions, both sub-exponentially secure — BPR15 — polynomially secure iO and one-way permutations — GPS16 — or sub-exponential LWE — JKKZ21.
• PPP (Polynomial Pigeonhole Principle): contains the problem of finding either a preimage of $0^n$ or a collision in a function $f:\{0,1{\}}^n\to \{0,1{\}}^n$ (pigeonhole guarantees one exists) — Pap94. Integer factorization reduces to the PPP problem WeakPigeon in randomized polynomial time, and deterministically under the generalized Riemann hypothesis — Jer16. Suitable formulations of discrete logarithm in general groups are PPP-complete — HV21.
• PPA (Polynomial Parity Argument): related to graph parity arguments. Integer factorization reduces to a PPA problem in randomized polynomial time, and deterministically under the generalized Riemann hypothesis — Jer16.
• PLS (Polynomial Local Search): finding local optima. Contains many optimization problems.
• CLS (Continuous Local Search): finding approximate local optima of continuous functions; $\mathbf{CLS}\subseteq \mathbf{PPAD}\cap \mathbf{PLS}$ — DP11.

PPAD

The class of total search problems reducible to End-of-Line: given circuits $S,P:\{0,1{\}}^n\to \{0,1{\}}^n$ with $P(0^n)=0^n\ne S(0^n)$, find $x$ with $P(S(x))\ne x$, or with $S(P(x))\ne x\ne 0^n$ — Pap94. PPAD is hard on average if some efficiently samplable distribution over End-of-Line instances is such that every efficient algorithm outputs a solution with negligible probability.

CLS

The class of total search problems reducible to Continuous-Local-Opt: given circuits computing a potential $p$ and a map $f$ on the unit cube, both claimed to be $\lambda$-Lipschitz, and $\epsilon >0$, find an approximate local optimum, a point $x$ with $p(f(x))\ge p(x)-\epsilon$, or two points witnessing that $p$ or $f$ is not $\lambda$-Lipschitz — DP11. It contains End-of-Metered-Line, an End-of-Line instance $(S,P)$ given together with a circuit $V$ claimed to give each vertex’s distance from $0^n$ along its line, whose solutions are the ends of lines and the vertices where $V$ is locally inconsistent with $S$ and $P$ — HY17. CLS is hard on average if some efficiently samplable distribution over instances of a problem in CLS is such that every efficient algorithm outputs a solution with negligible probability — standard.

PPP

The class of total search problems reducible to Pigeon: given a circuit $C:\{0,1{\}}^n\to \{0,1{\}}^n$, find $x$ with $C(x)=0^n$ or a collision $x\ne y$, $C(x)=C(y)$ — Pap94.

PWPP

The class of total search problems reducible to Weak Pigeon: given a circuit $C:\{0,1{\}}^n\to \{0,1{\}}^{n-1}$, find a collision. The class is due to Jer16; $\mathbf{PWPP}\subseteq \mathbf{PPP}$, and a collision-resistant hash function family is a hard-on-average PWPP problem — standard.

PWPP under randomized reductions

The total search problems that reduce to Weak Pigeon by a randomized polynomial-time reduction succeeding with noticeable probability, repeatable since solutions are checkable. It contains PWPP, and Jer16 put factoring in it — Jer16.

PPA

The class of total search problems reducible to Leaf: given a circuit describing an undirected graph of maximum degree two with a degree-one vertex $0^n$, find another vertex of degree one — Pap94.

PPA under randomized reductions

The total search problems that reduce to Leaf by a randomized polynomial-time reduction succeeding with noticeable probability. It contains PPA, and Jer16 put factoring in it — Jer16.

Known relationships

• $\mathbf{P}\subseteq \mathbf{FP}\subseteq \mathbf{TFNP}\subseteq \mathbf{FNP}$.
• No TFNP problem is NP-hard unless NP = coNP (Megiddo–Papadimitriou, TCS 1991).

Relevance to cryptography

Integer factorization and discrete logarithm — the two most historically important hard problems in cryptography — are both in TFNP, formalizing the intuition that they are “hard search problems with guaranteed solutions.” Recent work derives hardness of TFNP subclasses (especially PPAD) from cryptographic assumptions: PPAD is hard assuming indistinguishability obfuscation and one-way functions, both sub-exponentially secure — BPR15.

Participates in

Builds on Total function NP

• CLS hardness ⇒ PPAD hardness (via CLS)
• PPA ⊆ PPA under randomized reductions (via PPA)
• PPA ⊆ TFNP (via PPA)
• PPP ⊆ TFNP (via PPP)
• PWPP ⊆ PPP (via PWPP)
• PWPP ⊆ PWPP under randomized reductions (via PWPP)

Produces Total function NP

• CLS hardness ⇒ PPAD hardness (via PPAD)
• DLOG ∈ PWPP (via PWPP)
• DLOG ⊆ TFNP
• FAC ∈ PPA (under randomized reductions) (via PPA under randomized reductions)
• FAC ∈ PWPP (under randomized reductions) (via PWPP under randomized reductions)
• FAC ⊆ TFNP
• iO + OWP ⇒ CLS hardness (via CLS)
• iO + OWP ⇒ PPAD hardness (via PPAD)
• PPA ⊆ PPA under randomized reductions (via PPA under randomized reductions)
• PPA ⊆ TFNP
• PPP ⊆ TFNP
• PWPP ⊆ PPP (via PPP)
• PWPP ⊆ PWPP under randomized reductions (via PWPP under randomized reductions)
• SIS ∈ PWPP (via PWPP)
• Sub-exponential OWF + iO ⇒ PPAD hardness (via PPAD)
• Sub-exponential DDH ⇒ PPAD hardness (via PPAD)
• Sub-exponential LWE ⇒ PPAD hardness (via PPAD)

Barriers

• No fully-black-box reduction from PPAD hardness + OWF to KE (via PPAD)
• No fully-black-box reduction from PPAD hardness to OWF (via PPAD)