Even harder pseudovariety membership problem

Marcel Jackson

arxiv: 2606.23723 · v1 · pith:5YCU5J5Hnew · submitted 2026-06-19 · 🧮 math.LO · cs.CC

Even harder pseudovariety membership problem

Marcel Jackson This is my paper

Pith reviewed 2026-06-26 12:59 UTC · model grok-4.3

classification 🧮 math.LO cs.CC

keywords pseudovarietysemigroupmembership problemDifference Pcomputational complexityfinite algebradecision problemalgebraic structure

0 comments

The pith

A finite semigroup exists such that membership in its generated pseudovariety is hard for Difference P.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs one specific finite semigroup S and proves that the problem of deciding whether a given finite semigroup belongs to the pseudovariety generated by S is hard for Difference P. Difference P contains decision problems expressible as the symmetric difference of two NP sets and sits above NP in the polynomial hierarchy. A sympathetic reader cares because the result places a natural algebraic decision problem at a higher level of complexity than earlier NP-hardness results for pseudovariety membership.

Core claim

We present a finite semigroup whose pseudovariety has membership problem hard for the class Difference P. The argument proceeds by exhibiting an explicit finite semigroup together with a polynomial-time reduction from a known Difference P-complete problem to the question of whether an arbitrary finite semigroup lies in the pseudovariety generated by the exhibited semigroup.

What carries the argument

The finite semigroup S constructed in the paper, together with the polynomial-time reduction from a Difference P-complete problem to membership testing in the pseudovariety generated by S.

If this is right

The membership problem for the pseudovariety lies outside P unless P equals Difference P.
Some pseudovarieties generated by a single finite semigroup require computational resources at the second level of the polynomial hierarchy.
The hierarchy of known hardness results for pseudovariety membership problems is strict at least up to Difference P.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar constructions may lift hardness results for other algebraic varieties or for problems outside semigroup theory.
If the reduction technique generalizes, it could separate the complexity of membership for different generating semigroups more finely.
The result raises the question whether every pseudovariety generated by a finite semigroup has membership in some fixed level of the polynomial hierarchy.

Load-bearing premise

The explicit construction of the semigroup and the correctness of the reduction from a Difference P-complete problem to the membership question are both valid.

What would settle it

Either a polynomial-time algorithm deciding membership for the pseudovariety generated by the presented semigroup, or an explicit counterexample showing that the reduction maps some no-instance to a yes-instance.

read the original abstract

We present a finite semigroup whose pseudovariety has membership problem hard for the class \emph{Difference P}

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Jackson gives an explicit finite semigroup making pseudovariety membership Difference P-hard.

read the letter

Jackson presents a finite semigroup S such that deciding membership in the pseudovariety generated by S is hard for Difference P. That is the central claim and the main new piece.

The work improves on earlier results by reaching this level in the boolean hierarchy. It supplies a concrete example rather than an abstract existence argument, which is the useful part for people tracking these complexity bounds.

The paper states the claim cleanly and relies on standard semigroup and complexity notions. The stress-test note finds no internal inconsistency or misapplication of pseudoidentity or reduction ideas, so nothing in the statement itself looks broken.

The main soft spot is that the abstract is one sentence long. Without the actual semigroup and the polynomial reduction from a Difference P-complete problem, it is impossible to check whether the construction works or whether the reduction is tight. If the full text contains those details and they hold, the result stands; if they do not, the claim collapses. That is the only real uncertainty.

The paper is aimed at the small group of researchers who work on the computational complexity of semigroup pseudovarieties. A reader outside that niche will not get much from it.

It should go to peer review. The claim is specific, the target class is higher than previous known cases, and referees in the area can verify the construction in reasonable time.

Referee Report

1 major / 0 minor

Summary. The manuscript claims to present a finite semigroup S such that the membership problem for the pseudovariety generated by S is hard for the complexity class Difference P.

Significance. If the claim were supported by a concrete construction and a valid reduction, it would establish a new lower bound for pseudovariety membership problems, placing them in the boolean hierarchy at the level of Difference P. This would be a notable extension of known complexity results for algebraic decision problems in semigroup theory.

major comments (1)

The manuscript consists solely of the one-sentence abstract asserting the existence of such a semigroup and the hardness result. No explicit finite semigroup is exhibited, no pseudovariety is defined via pseudoidentities or generators, and no polynomial-time reduction from a known Difference P-complete problem (such as a variant of SAT-UNSAT) to the membership question is provided. This absence makes the central claim unverifiable and unsupported.

Simulated Author's Rebuttal

1 responses · 1 unresolved

We thank the referee for the report. We agree that the submitted manuscript contains only the one-sentence claim and supplies neither an explicit semigroup nor a reduction.

read point-by-point responses

Referee: The manuscript consists solely of the one-sentence abstract asserting the existence of such a semigroup and the hardness result. No explicit finite semigroup is exhibited, no pseudovariety is defined via pseudoidentities or generators, and no polynomial-time reduction from a known Difference P-complete problem (such as a variant of SAT-UNSAT) to the membership question is provided. This absence makes the central claim unverifiable and unsupported.

Authors: The observation is correct: the manuscript provides no construction, no generators or pseudoidentities, and no reduction. The central claim therefore cannot be verified from the text as submitted. revision: yes

standing simulated objections not resolved

Explicit construction of the finite semigroup S, definition of the pseudovariety it generates, and the polynomial-time reduction establishing Difference P-hardness, none of which appear in the manuscript.

Circularity Check

0 steps flagged

No circularity; direct construction of semigroup and reduction presented

full rationale

The paper's central claim is the explicit presentation of a finite semigroup S together with a polynomial-time reduction establishing that membership in the pseudovariety generated by S is Difference P-hard. No equations, definitions, or self-citations are invoked that reduce the claimed hardness result to a fit, renaming, or prior result by the same authors. The derivation chain consists of a concrete semigroup construction and a standard complexity reduction from a known Difference P-complete problem; both steps are external to any input data or self-referential definitions within the paper. This is the normal case of a self-contained existence proof in semigroup theory and complexity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no information on any free parameters, axioms, or invented entities used in the proof or construction.

pith-pipeline@v0.9.1-grok · 5514 in / 1011 out tokens · 39903 ms · 2026-06-26T12:59:40.263069+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

8 extracted references · 1 canonical work pages

[1]

Chang and J

R. Chang and J. Kadin, The Boolean hierarchy and the polynomial hierarchy: A closer connection, in
[2]

Jackson, Flexible constraint satisfiability and a problem in semigroup theory, Internat

M. Jackson, Flexible constraint satisfiability and a problem in semigroup theory, Internat. J. Algebra Comput. 35 (2025), 771--821

2025
[3]

Jackson and R

M. Jackson and R. McKenzie, Interpreting graph colorability in finite semigroups, Int. J. Algebra Comput. 16 (2005), 119--140

2005
[4]

Kadin, The Polynomial Time Hierarchy collapses if the Boolean hierarchy collapses, SIAM J

J. Kadin, The Polynomial Time Hierarchy collapses if the Boolean hierarchy collapses, SIAM J. Comput. 17 (1988), 1263--1282; erratum in SIAM J. Comput. 20 (1991), p. 404

1988
[5]

Kl\' ma, M

O. Kl\' ma, M. Kunc and L. Pol\' a k, Deciding k -piecewise testability, Internat. J. Algebra Comput. (2026), doi.org/10.1142/S0218196726500359

work page doi:10.1142/s0218196726500359 2026
[6]

Kozik, A 2EXPTIME complete varietal membership problem, SIAM J

M. Kozik, A 2EXPTIME complete varietal membership problem, SIAM J. Comput. 38 (2009), 2443--2467

2009
[7]

Simon, Hierarchies of events of dot-depth one, Ph.D

I. Simon, Hierarchies of events of dot-depth one, Ph.D. thesis, University of Waterloo (1972)

1972
[8]

M. V. Volkov, Reflexive relations, extensive transformations and piecewise testable languages of a given height, Internat. J. Comput. 14 (2004), 817--827

2004

[1] [1]

Chang and J

R. Chang and J. Kadin, The Boolean hierarchy and the polynomial hierarchy: A closer connection, in

[2] [2]

Jackson, Flexible constraint satisfiability and a problem in semigroup theory, Internat

M. Jackson, Flexible constraint satisfiability and a problem in semigroup theory, Internat. J. Algebra Comput. 35 (2025), 771--821

2025

[3] [3]

Jackson and R

M. Jackson and R. McKenzie, Interpreting graph colorability in finite semigroups, Int. J. Algebra Comput. 16 (2005), 119--140

2005

[4] [4]

Kadin, The Polynomial Time Hierarchy collapses if the Boolean hierarchy collapses, SIAM J

J. Kadin, The Polynomial Time Hierarchy collapses if the Boolean hierarchy collapses, SIAM J. Comput. 17 (1988), 1263--1282; erratum in SIAM J. Comput. 20 (1991), p. 404

1988

[5] [5]

Kl\' ma, M

O. Kl\' ma, M. Kunc and L. Pol\' a k, Deciding k -piecewise testability, Internat. J. Algebra Comput. (2026), doi.org/10.1142/S0218196726500359

work page doi:10.1142/s0218196726500359 2026

[6] [6]

Kozik, A 2EXPTIME complete varietal membership problem, SIAM J

M. Kozik, A 2EXPTIME complete varietal membership problem, SIAM J. Comput. 38 (2009), 2443--2467

2009

[7] [7]

Simon, Hierarchies of events of dot-depth one, Ph.D

I. Simon, Hierarchies of events of dot-depth one, Ph.D. thesis, University of Waterloo (1972)

1972

[8] [8]

M. V. Volkov, Reflexive relations, extensive transformations and piecewise testable languages of a given height, Internat. J. Comput. 14 (2004), 817--827

2004