Paper 2018/1178

Pseudo-Free Families of Computational Universal Algebras

Mikhail Anokhin

Abstract

Let $\mathrm{\Omega }$ be a finite set of finitary operation symbols. We initiate the study of (weakly) pseudo-free families of computational $\mathrm{\Omega }$-algebras in arbitrary varieties of $\mathrm{\Omega }$-algebras. Most of our results concern (weak) pseudo-freeness in the variety $\mathfrak{O}$ of all $\mathrm{\Omega }$-algebras. A family $(H_d{)}_{d\in D}$ of computational $\mathrm{\Omega }$-algebras (where $D\subseteq \{0,1{\}}^{\ast }$) is called polynomially bounded (resp., having exponential size) if there exists a polynomial $\eta$ such that for all $d\in D$, the length of any representation of every $h\in H_d$ is at most $\eta (|d|)$ (resp., $|H_d|\le 2^{\eta (|d|)}$). First, we prove the following trichotomy: (i) if $\mathrm{\Omega }$ consists of nullary operation symbols only, then there exists a polynomially bounded pseudo-free family in $\mathfrak{O}$; (ii) if $\mathrm{\Omega }={\mathrm{\Omega }}_0\cup \{\omega \}$, where ${\mathrm{\Omega }}_0$ consists of nullary operation symbols and the arity of $\omega$ is $1$, then there exist an exponential-size pseudo-free family and a polynomially bounded weakly pseudo-free family (both in $$); (iii) in all other cases, the existence of polynomially bounded weakly pseudo-free families in $$ implies the existence of collision-resistant families of hash functions. Second, assuming the existence of collision-resistant families of hash functions, we construct a polynomially bounded weakly pseudo-free family and an exponential-size pseudo-free family in the variety of all $$-ary groupoids, where $$ is an arbitrary positive integer. In particular, for arbitrary $$, polynomially bounded weakly pseudo-free families in the variety of all $$-ary groupoids exist if and only if collision-resistant families of hash functions exist.

Note: We have added a reference to the journal version of the paper and made some other minor changes.