Polynomially Complete Quasigroups of Prime Order

Abstract

We formulate a polynomial completeness criterion for quasigroups of prime order, and show that verification of polynomial completeness may require time polynomial in order. The results obtained are generalized to n-quasigroups for any n ≥ 3. In conclusion, simple corollaries are given on the share of polynomially complete quasigroups among all quasigroups, and on the cycle structure of row and column permutations in Cayley tables for quasigroups that are not polynomially complete.