  The constraint satisfaction problem (CSP) can be formulated as a homomorphism
problem between relational structures: given a structure $\mathcal{A}$, for any
structure $\mathcal{X}$, whether there exists a homomorphism from $\mathcal{X}$
to $\mathcal{A}$. For years, it has been conjectured that all problems of this
type are divided into polynomial-time and NP-complete problems, and the
conjecture was proved in 2017 separately by Zhuk (2017) and Bulatov (2017).
Zhuk's algorithm solves tractable CSPs in polynomial time. The algorithm is
partly based on universal algebra theorems: informally, they state that after
reducing some domain of an instance to its strong subuniverses, a satisfiable
instance maintains a solution.
  In this paper, we present the formalization of the proofs of these theorems
in the bounded arithmetic $W^1_1$ introduced by Skelley (2004). The
formalization, together with our previous results (2022), shows that $W_1^1$
proves the soundness of Zhuk's algorithm, where by soundness we mean that any
rejection of the algorithm is correct. From the known relation of the theory to
propositional calculus $G$, it follows that tautologies, expressing the
non-existence of a solution for unsatisfiable instances, have short proofs in
$G$.
