Herbrand consistency search form of the TFNP conjecture

Let T\mathcal T be the class of theories under consideration. For a consistent universal sentence Φ\Phi, let HCS(Φ)HCS(\Phi) be its Herbrand Consistency Search problem: given finitely many tuples of terms, find a truth assignment to the relevant atomic subformulas making the corresponding instances of Φ\Phi true. Herbrand consistency search TFNP conjecture. For every TTT\in\mathcal T, there exists a consistent universal sentence Φ\Phi such that HCS(Φ)HCS(\Phi) is not polynomially reducible to any TFNP problem provably total in TT, equivalently HCS(Φ)TFNP(T)HCS(\Phi)\notin\operatorname{TFNP}^*(T). This is an equivalent Herbrand-search formulation of the TFNP conjecture.

Sources & referencesView supporting material

Primary source

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

Additional references

2 papers in this index state this conjecture (2010–2016). The statement above is taken from the most recent of them; the others are arXiv:1008.0225.

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.