__
TR22-120 | 24th August 2022 13:23
__

#### On the existence of strong proof complexity generators

**Abstract:**
The working conjecture from K'04 that there is a proof complexity generator hard for all

proof systems can be equivalently formulated (for p-time generators) without a reference to proof complexity notions

as follows:

\begin{itemize}

\item There exist a p-time function $g$ extending each input by one bit such that its range $rng(g)$

intersects all infinite NP sets.

\end{itemize}

We consider several facets of this conjecture, including its links to bounded arithmetic (witnessing and

independence results) and the range avoidance problem,

to time-bounded Kolmogorov complexity, to feasible disjunction property of propositional proof

systems and to complexity of proof search.

We argue that a specific gadget generator from K'08 is a good candidate for $g$.