Papadimitriou–Yannakakis' completeness conjecture for minimum generating sets of quasigroups
Statement
A quasigroup is an algebra whose multiplication table is a Latin square; equivalently, for all elements , there are unique elements such that and . The minimum generating set problem asks whether a given quasigroup has a generating set of size at most , where is the order of the quasigroup.
Papadimitriou–Yannakakis' conjecture. The minimum generating set problem for quasigroups is -complete.
Papadimitriou and Yannakakis established the analogous completeness result for arbitrary magmas and conjectured that completeness persists for the more structured class of quasigroups. The paper reports an unconditional refutation of a version of this conjecture for completeness under quasi-polynomial-size constant-depth reductions, and a refutation under polylogarithmic-space reductions assuming , so the conjecture is treated as refuted.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.