4 problems

By a generator $g$ we mean a map whose restriction $g_n$ to $\{0,1\}^n$ has range contained in $\{0,1\}^m$, where $m=m(n)>n$, and is computed by a circuit of size $m^{O(1)}$. For…

Let $\mathcal{S}$ be a theory, let $\phi$ be a sentence, and let $n$ be a natural number. Write $Con_{\mathcal{S}+\phi}(n)$ for the bounded consistency statement for…

Let $A$ be a set of atoms, let $b$ be a test, and let $\mathsf{SGKAT}$ be the cyclic proof system for Guarded Kleene Algebra with Tests described in the paper. Let…

Let $\mathsf{KS}$ be the minimal complete fragment of a standard deep inference system for propositional logic, and let $\mathsf{KS}\cup\{\mathsf{c\!\uparrow}\}$ be its extension b…