You have to be careful about what you mean by "linear"—linear programs are P-complete, and all binary operations are linear over F_2 (including NAND, etc), sinc

You have to be careful about what you mean by "linear"—linear programs are P-complete, and all binary operations are linear over F_2 (including NAND, etc), since all functions are polynomials over finite fields and the largest polynomial over F_2 is of degree 2-1=1. There are many linear elements which can generate arbitrary circuits and hence can (in principle!) implement any finite circuit (e.g., processor). I do agree, though, that in this case it's unclear how the 'coprocessor' connection arises from the original statement given in the paper.