Diagonalization in proof complexity
Jan Krajı́ček · Fundamenta Mathematicae · 2004
We study diagonalization in the context of implicit proofs of [10]. We prove that at least one of the following three conjectures is true: $\bullet$ There is a function $f : \{0, 1\}^{*} \rightarrow \{0,1\}$ computable in ${\cal E}$ that has circuit