We provide a list of new natural VNP-intermediate polynomial families, based on basic (combinatorial) NP-complete problems that are complete under \emph{parsimonious} reductions. Over finite fields, these families are in VNP, and under the plausible hypothesis Mod p P P poly , are neither VNP-hard (even under oracle-circuit reductions) nor in VP. Prior to this, only the Cut Enumerator polynomial was known to be VNP-intermediate, as shown by B\"{u}rgisser in 2000.

We next show that over rationals and reals, two of our intermediate polynomials, based on satisfiability and Hamiltonian cycle, are not monotone affine polynomial-size projections of the permanent. This augments recent results along this line due to Grochow.

Finally, we describe a (somewhat natural) polynomial defined independent of a computation model, and show that it is VP-complete under polynomial-size projections. This complements a recent result of Durand et al.\ (2014) which established VP-completeness of a related polynomial but under constant-depth oracle circuit reductions. Both polynomials are based on graph homomorphisms. Variants yield families similarly complete for VBP and VNP.