The complexity of checking the polynomial completeness of finite quasigroups

DOI10.1515/DMA-2020-0016MaRDI QIDQ783116zbMATH OpenOpenAlexFDO

Authors Aleksey V. Galatenko, Anton E. Pankratiev

Publication date 30 July 2020

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma-2020-0016

zbMATH Keywords

Latin squarepolynomial completenessquasigroup

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Loops, quasigroups (20N05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Polynomially complete quasigroups of prime order
• Checking quasi-identities in a finite semigroup may be computationally hard.
• Efficient verification of polynomial completeness of quasigroups
• On n-ary polynomially complete quasigroups
• scientific article; zbMATH DE number 6288955

Cites work

• Characterization of polynomially complete quasigroups based on Latin squares for cryptographic transformations
• Function Algebras on Finite Sets
• scientific article; zbMATH DE number 3775602 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 6761101 (Why is no real title available?)
• scientific article; zbMATH DE number 6288955 (Why is no real title available?)
• Polynomially complete quasigroups of prime order
• The number of square islands on a rectangular sea

Cited in

(7)

• Polynomially complete quasigroups of prime order
• Strong polynomial completeness of almost all quasigroups
• Algorithms for checking some properties of \(n\)-quasigroups
• Efficient verification of polynomial completeness of quasigroups
• scientific article; zbMATH DE number 2077108 (Why is no real title available?)
• On n-ary polynomially complete quasigroups
• The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem

This page was built for publication: The complexity of checking the polynomial completeness of finite quasigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q783116)