{"id":"df047665-55a7-45a8-bd60-53a28c64237d","arxiv_id":"2502.10103","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For finite inverse semigroups, membership and conjugacy are easy (NC/NP or LOGSPACE) precisely for strict and Clifford varieties, and PSPACE-complete or L-complete otherwise.","lead":"This paper classifies how hard it is to test membership and conjugacy in finite inverse semigroups, a model of reversible partial computation. The answer depends on which variety the semigroup belongs to, with sharp dichotomies in both standard input models.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 57's membership reduction misapplies Lemma 55: configuration idempotents e(Cs), e(Ct) are not shown to lie in U_Gamma, and for locked NCL configurations e(Ct) is not in U_Gamma, so the extra generator (e(Ct),1) may create spurious memberships and the PSPACE-hardness of E-memb^sharps_PB(BM)…","rationale":"The reader's verdict is CONDITIONAL, and I agree that the paper needs revision, but my main concern differs from the reader's weakest assumption. The reader flagged Proposition 6 as a black box; that is a cited structural classification and is not a serious correctness risk. The reader also flagged Lemma 65 as assuming J-equivalence; however, the restricted variant conj^sharps_PB(V) explicitly requires s ~_S t, so the J-equivalence hypothesis is satisfied, and this concern does not land. The reader's citation issue in Corollary 61 (Lemma 20 vs. Lemma 31) is a minor error. The load-bearing concern I found is internal to the proof of Theorem 57's membership-hardness reduction: Lemma 55 is applied in a setting where its hypotheses are not verified, and there is concrete reason to think they fail for locked NCL configurations. This does not necessarily mean the theorem is false, but it means the proof as written leaves the PSPACE-hardness of E-memb^sharps_PB(BM) unsupported. Because this feeds directly into Theorem B's hardness direction, the central dichotomy claim should be accepted only conditionally on a corrected reduction or a direct verification that configuration idempotents are always in U_Gamma, or that the enlarged semigroup U'' introduces no false positives. My recommended verdict is therefore UNCHANGED (still CONDITIONAL), since the paper should address this gap in revision.","tokens_in":42757,"tokens_out":28946,"duration_ms":253843,"concrete_test":"Construct a small NCL machine with two configurations Cs and Ct in different connected components, where Ct is locked (no single edge can be reversed while preserving all vertex constraints). Build S_Gamma, U_Gamma, and U'_Gamma exactly as in Theorem 57, then test whether (e(Ct),0) belongs to U'_Gamma. If it does, the reduction is unsound. Independently, test whether e(Ct) belongs to U_Gamma; if it does not, the cited Lemma 55 cannot be applied with U=U_Gamma, confirming the proof gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the final paragraph of the proof of Theorem 57 (Section 7.1), the authors claim that (e(Ct),0) in U'_Gamma is equivalent to e(Cs) >=_J e(Ct) relative to U_Gamma, citing Lemma 55. But Lemma 55 requires both idempotents to lie in the inverse semigroup U with respect to which the J-order is taken. In the NCL construction, U_Gamma is generated solely by transition elements u(c1,c2'), and the configuration idempotents e(C) are elements of S_Gamma that need not belong to U_Gamma. Indeed, for a locked configuration Ct (one where no single edge reversal preserves all vertex in-flow constraints), no generator has a local configuration of Ct in its domain, so e(Ct) cannot be generated as a product of u u-bar terms; hence e(Ct) not in U_Gamma. The added generator (e(Ct),1) puts e(Ct) into the first-coordinate semigroup U'' = <U_Gamma, e(Ct)>, so a derivation of (e(Ct),0) in U'_Gamma would only show e(Cs) >=_J e(Ct) in U'', not in U_Gamma. This can allow false positives: a product using e(Ct) as a conjugating factor could certify membership even when Cs and Ct lie in different connected components of the NCL configuration graph. Since this step is the basis for PSPACE-hardness of the idempotent membership problem for BM, and hence for the membership half of Theorem B's 'otherwise PSPACE-complete' case, the central dichotomy is not fully proven as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the membership and conjugacy problems for finite inverse semigroups in the Cayley table model and in the partial bijection model, parametrized by varieties of finite inverse semigroups. The main results are dichotomies: in the Cayley table model, both problems are in NPOLYLOGTIME and in L for Clifford varieties and L-complete otherwise (Theorem A); in the partial bijection model, they are in NC (membership) and NP (conjugacy) for strict inverse semigroups and PSPACE-complete otherwise (Theorem B). The proof machinery includes an L-reduction of strict inverse semigroups to groups via Munn graphs, hardness reductions from NCL using the combinatorial Brandt monoid B1_2, and consequences for intersection non-emptiness of two-state inverse automata, subpower membership, minimum generating set, and equation satisfiability.","tokens_in":43010,"tokens_out":19207,"duration_ms":179664,"significance":"If the results stand, the paper provides a nearly complete complexity classification for two central algorithmic problems on finite inverse semigroups, sharpening earlier PSPACE-completeness results of Birget–Margolis and Jack and matching the group bounds of Babai–Luks–Seress. The main theorems come with full proofs, the reductions to ugap, NCL, and permutation-group membership are substantial, and the corollaries concerning two-state inverse automata and subpower membership are independently interesting. The reliance on the published pseudovariety lattice classification (Proposition 6) is a black box, but it is a well-attributed external result and I do not treat it as a gap. However, as detailed below, one load-bearing step in the membership-hardness part of Theorem B is not proved as written, so the dichotomy is not yet fully established.","major_comments":[{"comment":"The reduction defines U'_Gamma = <Sigma_Gamma x {1}, (e(Cs),0), (e(Ct),1)> and invokes Lemma 55 to conclude that (e(Ct),0) in U'_Gamma iff e(Cs) >=_J^{U_Gamma} e(Ct). Lemma 55, as stated and proved, applies only to a semigroup generated by (es,0) and U x {1}; it does not permit the extra generator (e(Ct),1). Because (e(Ct),1) is present, the converse direction of Lemma 55 yields only a factorization e(Ct)=u e(Cs) v with u,v in <U_Gamma, e(Ct)>^1, not with u,v in U_Gamma^1. Thus the claimed equivalence with the relative J-order in U_Gamma is not established, and the PSPACE-hardness of E-memb^sharp_PB(BM) is unproven as written. This step is load-bearing for the membership lower bound in Theorem B when V is not contained in SIS. Note that the mere fact that e(Cs), e(Ct) need not lie in U_Gamma is not by itself the obstruction: the proof of Lemma 55 actually works for relative J with idempotents of the ambient semigroup. The real issue is the extra generator (e(Ct),1). The gap appears repairable: one can remove the generator (e(Ct),1) and use a relative-J version of Lemma 55, or alternatively derive hardness of membPB(BM) from the independently proved PSPACE-completeness of the subpower membership problem for B1_2 (Theorem 59 / Corollary 61). Please repair the reduction or restructure the proof to make the dependency explicit.","section":"Section 7.1, proof of Theorem 57 (membership half)"}],"minor_comments":[{"comment":"The introductory paragraph of the minimum generating set section is duplicated almost verbatim; please remove the repetition.","section":"Section 8.1"},{"comment":"Lemma 55 is stated with the hypothesis es, et in E(U), but its proof establishes the relative-J version for idempotents of the ambient semigroup; please restate the lemma in the more general form to match its intended use and avoid ambiguity about the J-order being relative to U.","section":"Section 2.6 and Lemma 55"},{"comment":"Several displayed formulas involving inverses appear to be missing overbars in the text (e.g., the condition in Proposition 52 should read y u \\bar u \\bar y t = t). Please ensure all inverse symbols render correctly.","section":"Propositions 51 and 52"}],"recommendation":"major_revision","confidential_remarks":"The gap in the membership reduction of Theorem 57 is localized and, in my view, fixable either by deleting the extra generator (e(Ct),1) and generalizing Lemma 55 or by rerouting through the subpower membership result of Corollary 61. I therefore do not doubt the overall dichotomy, but the manuscript as submitted does not fully prove the membership half of Theorem B. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the Fleischer-Stober-Thumm-Weiss paper on membership and conjugacy in inverse semigroups. The main results are genuinely good: variety-wise dichotomies for both input models, with the Brandt monoid as the critical obstruction, and a clean reduction of strict inverse semigroups to the group case via Munn graphs. The upper-bound machinery (SLPs, Munn graphs, Reingold's L) is careful, and the two-state inverse automata intersection result is a nice dividend.\n\nThe conjugacy half of the PSPACE-hardness (Theorem 57) looks solid. The NCL encoding is standard, and the idempotent conjugacy equivalence is argued directly. But the membership half, where they derive PSPACE-hardness of E-memb^#_PB(BM), has a gap. They apply Lemma 55 to U_Gamma, e(Cs), e(Ct), but Lemma 55 as stated requires both idempotents to lie in U. In the NCL construction, configuration idempotents e(C) are elements of the ambient product S_Gamma, and it is not shown that they lie in the generated subsemigroup U_Gamma; for a locked configuration there is no transition, so certainly e(Ct) is not in U_Gamma. Moreover, the text adds (e(Ct),1) to the generator set of U'_Gamma, which is outside the scope of Lemma 55 and can change the relative J-order. So the proof as written does not establish (e(Ct),0) in U'_Gamma iff e(Cs) ~_{U_Gamma} e(Ct).\n\nThis looks repairable: generalize Lemma 55 to idempotents of the ambient semigroup, and drop the extraneous generator (e(Ct),1). The proof goes through with the same argument. But the fix needs to be explicit, because as it stands the PSPACE-hardness of membPB for varieties outside SIS--a load-bearing part of Theorem B--is not fully proven.\n\nMinor points: Corollary 61 cites Lemma 20 for the SIS characterization but should cite Lemma 31. The proof of Lemma 65 assumes the two idempotents are J-equivalent without handling the general case; also fixable but should be spelled out.\n\nBottom line: this is a substantial paper with real contributions. The central dichotomy is probably true, but the membership-hardness reduction needs a revision before I'd trust it. Send it to a serious referee; it deserves the attention, and the fix is small enough that a competent referee can verify it. I'd recommend engaging with it and asking for a revision.","headline":"Strong dichotomy paper with a real but repairable gap in the membership-hardness reduction; worth serious refereeing after a fix.","tokens_in":43662,"tokens_out":13222,"would_cite":true,"duration_ms":116873,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["20M18","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every variety of finite inverse semigroups, membership and conjugacy are either easy (NC/NP, or LOGSPACE) or PSPACE-complete, with two tiny Brandt semigroups as the only obstructions.","keywords":["inverse semigroups","membership problem","conjugacy problem","complexity dichotomy","Brandt semigroup","strict inverse semigroups","PSPACE-completeness","NC"],"falsifier":"Build the reduction of Section 7 on a small PSPACE-complete NCL machine and check, for every pair of configurations, that the two constructed idempotents are conjugate in the generated subsemigroup if and only if the configurations are connected by transitions; any mismatch would refute the gadget behind Theorem 57 and Corollary C. Equally conclusive would be a variety V not contained in SIS for which the partial-bijection membership problem can be solved in NP.","tokens_in":42447,"feed_emoji":"🧩","tokens_out":11706,"duration_ms":103669,"temperature":0.7,"pith_summary":"This paper tries to prove a complete complexity classification of two decision problems for finite inverse semigroups: whether a given element lies in a generated inverse subsemigroup, and whether two elements are conjugate inside it. The classification is parametrized by varieties of finite inverse semigroups (classes closed under products, subsemigroups, and quotients) and by two input models: generators given as partial bijections, or the whole semigroup given by a multiplication table. The central claim is a dichotomy: in the partial bijection model, membership is in NC and conjugacy is in NP exactly for strict inverse semigroups (the smallest variety containing all groups and the five-element combinatorial Brandt semigroup), and both problems are PSPACE-complete for every larger variety; in the Cayley table model, the two problems are in LOGSPACE and NPOLYLOGTIME for Clifford semigroups and LOGSPACE-complete for every variety containing the combinatorial Brandt semigroup B2. This matters because it draws a sharp, structural line between invertible computation that can be solved in parallel or logarithmic space and invertible computation that is as hard as any problem in polynomial space, and it transfers the same line to automata intersection, subpower membership, minimum generating sets, and equations.","feed_headline":"Two small semigroups decide when inverse semigroup problems turn hard","feed_subtitle":"Membership and conjugacy in inverse semigroups are NC or NP on one side of the line, PSPACE-complete on the other.","key_machinery":"The critical objects are the combinatorial Brandt semigroup B2 (five elements: all partial bijections of a two-element set of rank at most one) and its monoid B1_2 with an identity adjoined. B2 is the obstruction to LOGSPACE-easiness in the Cayley table model; B1_2 is the obstruction to NC/NP-easiness in the partial bijection model. The reduction for strict inverse semigroups is carried by the Munn graph M($\\Delta$;Sigma): given a U-invariant set of points $\\Delta$, its vertices are idempotents e_Delta u u-bar for those generators u whose domain meets every orbit in $\\Delta$, and an edge labeled u joins e_Delta u u-bar to e_Delta u-bar u. Paths in this graph encode conjugation of idempotents, and its connected components correspond to the natural equivalence classes of the semigroup; this lets the authors reduce membership and conjugacy in U to the corresponding problems in a single subgroup, and then to permutation groups. In the Cayley table model the key mechanism is the observation that strongly connected components of the Cayley graph of an inverse semigroup are undirected, reducing to undirected graph accessibility; for Clifford semigroups, polylogarithmic straight-line programs give the NPOLYLOGTIME upper bounds.","core_discovery":"The paper's main result is a dichotomy for the partial bijection model (Theorem B). If the variety V of finite inverse semigroups is contained in the variety SIS of strict inverse semigroups, then the membership problem membPB(V) is in NC and the conjugacy problem conjPB(V) is in NP. If V is not contained in SIS, which happens exactly when V contains the six-element combinatorial Brandt monoid B1_2, then both problems are PSPACE-complete. The companion Theorem A gives the Cayley table model: for V contained in the Clifford semigroups (where every element commutes with its inverse) both problems are in NPOLYLOGTIME and in L; otherwise, when V contains B2, both are L-complete. The paper also draws the consequences: intersection non-emptiness for inverse automata is PSPACE-complete even with two states, the subpower membership problem is in NC exactly for strict inverse semigroups and PSPACE-complete otherwise, and minimum generating set and equation satisfiability are in NP for strict inverse semigroups and PSPACE-complete otherwise.","pith_inferences":["The same B1_2 gadget is likely to make many other reachability-style problems over inverse semigroups PSPACE-complete exactly outside SIS, so the dichotomy may extend to rational subset membership and related problems without new ideas.","The two-state bound in Corollary C cannot be lowered to one state, since one-state inverse automata do not support the construction; a direct proof of that optimality would close the statement.","Making the lattice classification used in Proposition 6 constructive would turn the dichotomy into a decision procedure for the complexity class of a variety, since the algorithmic reductions themselves are already explicit.","A similar dichotomy for regular *-semigroups, posed as an open problem in the paper, would likely hinge on finding the analogues of B2 and B1_2 in that richer lattice; the NCL encoding used here is a natural template."],"forward_implications":["Two-state inverse automata have a PSPACE-complete intersection non-emptiness problem, so the hardness of invertible computation does not require many states.","For any inverse semigroup S, the subpower membership problem is solved in NC when S is strict and is PSPACE-complete otherwise; in particular there is no NP-complete intermediate case for inverse semigroups.","The minimum generating set problem and the equation satisfiability problem are in NP for varieties of strict inverse semigroups and PSPACE-complete for every other variety.","In the Cayley table model, membership and conjugacy are in NPOLYLOGTIME and LOGSPACE for Clifford varieties and LOGSPACE-complete otherwise; a variety of finite inverse semigroups admits polylogarithmic straight-line programs if and only if it consists of Clifford semigroups.","Within the easy side of the partial bijection model, the classification refines to AC0 for semilattices, L-completeness for the variety generated by B2, and NC/NP with L-hardness otherwise."],"supporting_citations":[{"why":"Establishes PSPACE-completeness of membership in the transformation semigroup model, the hard-side baseline for the partial bijection model.","marker":"[62]"},{"why":"Proves PSPACE-completeness of intersection non-emptiness for inverse automata, the basis for the automata corollary and prior hardness.","marker":"[16]"},{"why":"Gives an NC algorithm for membership in permutation groups, the target to which strict inverse semigroup membership is reduced.","marker":"[7]"},{"why":"Shows undirected graph accessibility is in logarithmic space, making the L-algorithms and L-reductions effective.","marker":"[89]"},{"why":"Introduces the PSPACE-complete nondeterministic constraint logic problem used as the source of the hardness reduction.","marker":"[46]"},{"why":"Provides the NPOLYLOGTIME membership algorithm for Clifford semigroups in the Cayley table model, reused as an upper bound in Theorem A.","marker":"[35]"},{"why":"Supplies the lattice classification of pseudovarieties of inverse semigroups that gives the dichotomy its exhaustive two-case split.","marker":"[44]"},{"why":"Gives polylogarithmic straight-line programs for finite groups, used for the NP conjugacy bound and the NPOLYLOGTIME upper bound.","marker":"[8]"}],"fun_headline_variants":["Strict inverse semigroups: membership in NC, otherwise PSPACE-complete","One small monoid B1_2 flips inverse semigroup problems from NC to PSPACE","Inverse semigroup dichotomy: easy if strict, PSPACE-complete if not","Membership and conjugacy in inverse semigroups: a clean complexity cliff"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The dichotomy rests on a black-box structural fact: every variety of finite inverse semigroups is either contained in the strict inverse semigroups or contains the six-element combinatorial Brandt monoid, and the paper does not prove that fact itself.","fun_headline_variants_meta":{"raw":{"variants":["Strict inverse semigroups: membership in NC, otherwise PSPACE-complete","One small monoid B1_2 flips inverse semigroup problems from NC to PSPACE","Inverse semigroup dichotomy: easy if strict, PSPACE-complete if not","Membership and conjugacy in inverse semigroups: a clean complexity cliff"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000241,"raw_usage":{"total_tokens":1602,"prompt_tokens":1104,"completion_tokens":498,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":720,"completion_tokens_details":{"reasoning_tokens":409}},"tokens_in":720,"tokens_out":498,"duration_ms":5180,"temperature":1.0,"reasoning_tokens":409,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T19:27:11.986770+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build the reduction of Section 7 on a small PSPACE-complete NCL machine and check, for every pair of configurations, that the two constructed idempotents are conjugate in the generated subsemigroup if and only if the configurations are connected by transitions; any mismatch would refute the gadget behind Theorem 57 and Corollary C. Equally conclusive would be a variety V not contained in SIS for which the partial-bijection membership problem can be solved in NP.","supporting_citations":[{"cited_title":"Birget , S","cited_arxiv_id":null,"evidence_quote":"Proves PSPACE-completeness of intersection non-emptiness for inverse automata, the basis for the automata corollary and prior hardness."},{"cited_title":"Babai, E","cited_arxiv_id":null,"evidence_quote":"Gives an NC algorithm for membership in permutation groups, the target to which strict inverse semigroup membership is reduced."},{"cited_title":"Reingold","cited_arxiv_id":null,"evidence_quote":"Shows undirected graph accessibility is in logarithmic space, making the L-algorithms and L-reductions effective."},{"cited_title":"u r F ormale M ethoden der I nformatik, U niversit \\","cited_arxiv_id":null,"evidence_quote":"Provides the NPOLYLOGTIME membership algorithm for Clifford semigroups in the Cayley table model, reused as an upper bound in Theorem A."},{"cited_title":"Babai and E","cited_arxiv_id":null,"evidence_quote":"Gives polylogarithmic straight-line programs for finite groups, used for the NP conjugacy bound and the NPOLYLOGTIME upper bound."}],"review_version":1}