FPRD LabShare an approach

← Claims

Theorem · complexity upper bound

FPRD-TM-T03

NP upper bound for minimum faithful permutation degree

Exact statement

Given two permutations on n points, deciding whether their generated group has a faithful permutation action of degree smaller than n belongs to NP.

StatusReconstructed from standard permutation-group algorithms; externally known
External reviewThe general NP upper bound is externally documented in the minimum faithful permutation-degree literature; no external review of this FPRD exposition is recorded.

Context

Every finite action is a disjoint union of transitive coset actions. A small faithful action can therefore be certified by a short list of subgroups.

Definitions

  • The action on (G/H_i) has degree ([G:H_i]) and kernel  Core_G(H_i).

Hypotheses and scope

  • The group is given by explicit permutation generators on n points.

Proof or evidence

Guess subgroups H_i with total index below n and trivial intersection of cores. Fewer than n subgroups suffice, and each has a generating set of polynomial size. Standard permutation-group algorithms verify membership, indices, coset actions, and triviality of the product-action kernel in polynomial time.

Coset-action certificate →

Verification notes

Certificate length and every required verification step were checked against the cited literature. The independent audit gives 76 small transformation-versus-permutation target agreements; the newer NC/RNC results for Fitting-free groups were not generalized to all two-generated groups. Evidence: /research-artifacts/result-review-2026-09-01-batch-18/independent-output.json

Limitations

  • No completeness or deterministic polynomial-time classification is claimed.
  • Two-generated groups need not be Fitting-free.

Open work

Determine whether the unrestricted two-generated group problem has a sharper deterministic bound; do not transfer the Fitting-free NC/RNC result without its hypothesis.