Conditional NP transfer through a compact poDFA action

Exact statement

If an $n$ -state L-trivial instance admits a polynomial-time computable faithful poDFA action $\rho:M^{\mathrm{op}}\hookrightarrow T_P$ of polynomial degree, explicit generator images, and a computable target code $t_f$ that equals $\rho(f)$ for positive instances and lies outside $\rho(M)$ for negative instances, then membership is in NP and positive instances have word certificates of length at most $|P|(|P|+1)/2$ .

StatusProved conditionally; the compact dual representation is not known in general

External reviewThe poDFA representative bound is a published MFCS 2024 result; no external review of this conditional FPRD transfer is recorded.

Context

Ryzhikov and Wolf prove a quadratic representative bound when the R-trivial action is already supplied as a poDFA. The theorem states exactly what is needed to transfer that result to the compact L-trivial input.

Hypotheses and scope

$|P|$ is polynomial in the original input size.
The action is faithful and its generator transformations are explicitly computable.
A target code $t_f$ is computable even when $f\notin M$ , equals $\rho(f)$ when $f\in M$ , and lies outside $\rho(M)$ otherwise.
A partial order witnessing the poDFA property is available.

Proof or evidence

Injectivity plus the total target-code condition preserves both positive and negative membership. The published poDFA bound supplies a quadratic-length representative, which can be guessed, evaluated in the explicit action, and reversed for multiplication in the original monoid.

Conditional NP theorem →

Verification notes

The target is an arbitrary transformation of Q and may lie outside M, so the revised statement no longer applies rho to an element outside its domain. Each representation and size assumption remains explicit.

Limitations

The theorem is not an unconditional NP upper bound for the original problem.
The right regular action may have exponentially many states.

Open work

Construct a polynomial-degree faithful action of the opposite monoid or prove that no uniform construction exists.