MathDBNo complete TFNP problem conjecture
No complete TFNP problem conjecture
A TFNP problem is a total polynomial search problem, and polynomial reduction is the usual polynomial-time reduction between search problems. No complete TFNP problem conjecture. There is no complete problem in TFNP; equivalently, there is no TFNP problem to which all TFNP problems can be reduced. This is presented as an equivalent, purely complexity-theoretic formulation of the TFNP conjecture.
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
Sign in to submit a solution.
No solutions have been posted yet.