TFNP non-completeness conjecture

About 10 years old · traced to

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 T∈TT\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.

References

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.