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

CREATORMarcel Jackson
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE6 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.23723

Browse the full library · About the Tower of Babel