TFNP non-completeness conjecture
TFNP non-completeness conjecture
Let be the class of theories under consideration. A TFNP problem is a total polynomial search problem, and is the class of such problems provably total in ; let be the problems polynomially reducible to members of . TFNP non-completeness conjecture. For every , there exists a TFNP problem that is not polynomially reducible to any TFNP problem provably total in , equivalently . 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 .
Sources & referencesView supporting material
Primary source
Pavel Pudlak, “Incompleteness in the finite domain”, arXiv:1601.01487 (2017).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.