Polynomial-time relative-degree algorithm

Exact statement

For an explicit rational linear representation, existence and value of the relative degree are decidable in deterministic polynomial time: compute $V$ and $W$ , test $0\le r<d$ , and return the unique candidate satisfying the safe-row conditions and $\lambda A^rB\gamma\ne0$ .

StatusProved; the reported bounded experiment is tracked separately because its checker is unavailable

External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

Invariant-space saturation and rational linear algebra replace quantification over all words. The dimension theorem bounds the candidate loop.

Definitions

Compute V by repeatedly adjoining M_c-images of the current basis until its dimension stops increasing.
Compute W as the simultaneous kernel of γ and the linear map p↦pB restricted to a basis of V.

Hypotheses and scope

The rational vectors and matrices are explicit and encoded in binary.

Proof or evidence

The safe-row lemma proves the support test, the dimension theorem proves completeness of the finite candidate range, and exact rational linear algebra gives polynomial bit complexity. The theorem does not depend on the separately recorded, currently unreproducible finite experiment.

Algorithm and correctness proof →

Verification notes

The correctness proof, exact bit-complexity scope, historical experiment, and reproducible exhaustive replacement were reviewed separately; neither finite computation replaces the proof.

Limitations

The stated complexity excludes translation from an arbitrary rational-expression syntax.
No novelty or external-review claim is made.

Open work

Send the public proof to Lorenzo Clemente for review after confirming a contact address and obtaining send-time approval.