FPRD LabShare an approach

← Claims

Theorem · complexity upper bound

FPRD-TM-T01

PSPACE upper bound for transformation degree

Exact statement

Given two transformations on n points, deciding whether their generated monoid embeds in T_m for some m<n belongs to PSPACE.

StatusProved; no matching hardness result is claimed
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

A candidate smaller pair can be enumerated in polynomial space. The main issue is deciding equality of the two induced word kernels without expanding either monoid.

Definitions

  • For a word (w), store the paired value (ηs(w),ηt(w))∈Tn×Tm(η_s(w),η_t(w))\in T_n\times T_m.

Hypotheses and scope

  • The generators and candidate target transformations are explicitly listed.
  • The full input generator list may also be used, provided its length is polynomial in the input size.

Proof or evidence

There are at most n^n m^m paired values. If the kernels differ, two shortest paired-value representatives below that bound witness the difference. A nondeterministic machine streams both words while retaining four transformations and logarithmic counters, giving NPSPACE; complement closure and enumeration of candidate targets yield PSPACE.

Polynomial-space kernel comparison →

Verification notes

The witness replacement, counter sizes, complement step, and workspace reuse were checked. An independent enumeration verifies 12,409 paired-kernel cases and the shortest-representative bound in every case; exponential time is allowed because only space is bounded.

Limitations

  • The theorem is an upper bound only.
  • Known PSPACE-complete problems for transformation semigroups do not supply hardness for this problem without a reduction.

Open work

Search for a matching lower bound or a sharper algorithm on structural subclasses without importing unrelated semigroup hardness.