Since equivalence of deterministic VPA can be checked in polynomial
time [1]}, it is clear that MinVPA belongs to NP.
We show hardness through an intermediate problem called MinImmersion.
We first prove that MinImmersion reduces to MinVPA (Proposition REF ),
and then show that MinImmersion is NP-hard, by
reduction from 3-colorability of graphs (Section ).
