$L$ be a language in ${\mathord{\it NP}}$ and $w\in \{0,1\}^*$. Trautwein [@lp-95-01] provided an R-AVG $G$ and a reduction that maps any formula $F$ onto a string $w_F$ s.t. $G\stackrel{*}{\Rightarrow}w_F$ iff $F\in\mathord{\it SAT}$. It was also shown that any R-AVG has a nondeterministic polynomial time, hence deterministic exponential time, recognition algorithm. Suppose every R-AVG $G$ has a grammar in ${\cal C}$. Then there exists a $G' \in {\cal C}$ with $L(G')=L(G)$. We can decide in polynomial time whether $w_F\in L(G)$ for any $w_F$. So, ${\mathord{\it P}}={\mathord{\it NP}}$.

If every R-AVG $G$ has a grammar in ${\cal C}$, then the algorithm for deciding “$w\in L$?” consists of: use Cook’s reduction to produce a formula $F$ that is satisfiable iff $w\in L$; use Trautwein’s reduction to produce $w_F$ and R-AVG $G$; enumerate grammars in $\cal C$ for the first grammar $G'$ that has a description of length less than $\log\log{\mathopen|w\mathclose|}$ for which $L(G)\cap\{0,1\}^{\leq\log\log{{\mathopen|w\mathclose|}}}=L(G')
\cap\{0,1\}^{\leq\log\log{{\mathopen|w\mathclose|}}}$ accept iff $w\in L(G')$. This gives a polynomial time algorithm that erroneously accepts or rejects $w$ for only a finite number of strings $w$. The theorem now follows from the fact that both ${\mathord{\it P}}$ and ${\mathord{\it NP}}$ are closed under finite variation.

If R-AVGs generate only context 