TFNP non-completeness conjecture

Let T\mathcal T be the class of theories under consideration. A TFNP problem is a total polynomial search problem, and TFNP(T)\operatorname{TFNP}(T) is the class of such problems provably total in TT; let TFNP(T)\operatorname{TFNP}^*(T) be the problems polynomially reducible to members of TFNP(T)\operatorname{TFNP}(T). TFNP non-completeness conjecture. For every TTT\in\mathcal T, there exists a TFNP problem PP that is not polynomially reducible to any TFNP problem provably total in TT, equivalently TFNP(T)TFNP\operatorname{TFNP}^*(T)\ne\operatorname{TFNP}. This conjecture seeks a total polynomial search problem whose complexity is not captured, even up to polynomial reduction, by the problems provably total in any fixed theory TT.

Sources & referencesView supporting material

Primary source

Pavel Pudlak, “Incompleteness in the finite domain”, arXiv:1601.01487 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.