ON COMPLETING PARTIAL GROUPOIDS TO SEMIGROUPS
P. Goralčík, Vácłav Koubek · International Journal of Algebra and Computation · 2006
Let [Formula: see text] be a class of semigroups containing all finite commutative bands, and let p(x) be a real polynomial. The [Formula: see text]-completion problem asks whether for a given partial groupoid G there exists a semigroup [Formula: see text] such that G ⊆ S, every product for (a, b) ∈ G2 defined in G coincides with that for (a, b) in S, and |S| ≤ p(|G|). We prove the problem to be ℕℙ-hard in general and ℕℙ-complete if the membership problem for [Formula: see text] is in ℙ.