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 squarequasigrouppolynomial completeness

Mathematics Subject Classification ID

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

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

• 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?)
• Characterization of polynomially complete quasigroups based on Latin squares for cryptographic transformations
• Function Algebras on Finite Sets
• Polynomially complete quasigroups of prime order
• The number of square islands on a rectangular sea

Cited in

(7)

• 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
• Polynomially complete quasigroups of prime order

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)