Han-Lin Ren

Many Proof Complexity Generators Inside One Demi-Bits Generator

For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N>10n$), we say that $G$ is a *proof complexity generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the (suitably encoded) statement"$y\not\in\mathrm{Range}(G)$"for every $y \in \{0, 1\}...