Even harder pseudovariety membership problem
Marcel Jackson · 2026
Read Even harder pseudovariety membership problem by Marcel Jackson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-23723.txt.
Description
Jackson sharpens a hardness result about deciding membership in families of finite algebraic structures, in a 2026 note on semigroup theory. A semigroup is a set with an associative operation, like combining moves in a game. A pseudovariety is a family of finite semigroups closed under natural constructions, and the membership problem asks whether a given semigroup belongs to the family one fixed example generates. Earlier work showed this problem can be NP hard.
Jackson constructs the test case from two ingredients multiplied together. One is the six element Brandt monoid, and the other is a monoid of order preserving maps on a short chain of numbers. For chain length at least four, deciding membership for the combined generator is hard for Difference P. That class contains both NP and its complement, so the problem exceeds either earlier benchmark alone.
Catalog record
| CREATOR | Marcel Jackson |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 6 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.23723