Existence of a p-time generator whose range intersects every infinite P set

Let gg be a polynomial-time function that maps inputs of length nn to outputs of length n+1n+1, and let rng(g)rng(g) denote its range. Proof search conjecture. There exists such a function gg whose range intersects every infinite P{\cal P} set; equivalently, the complement of rng(g)rng(g) is P{\cal P}-immune. The source presents this as equivalent to the conjecture that there is a uniform generator search-hard for all proof systems, obtained by replacing NP{\cal N}{\cal P} sets with P{\cal P} sets in the proof-search formulation. Its status is left open in the source.

Sources & referencesView supporting material

Primary source

Jan Krajicek, “On the existence of strong proof complexity generators”, arXiv:2208.11642 (2023).

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.