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 $\text{Mod}_pP \not\subseteq P/\text{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.

Added a VNP-complete family of homomorphism polynomials

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 $\text{Mod}_pP \not\subseteq P/\text{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,
the clique polynomial cannot be obtained as a monotone $p$-projection
of the permanent polynomial, thus ruling out the possibility of
transferring monotone clique lower bounds to the permanent. We also
show that two of our intermediate
polynomials, based on satisfiability and Hamiltonian cycle, are not
monotone affine polynomial-size projections of the permanent. These
results augment 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. A
simple restriction yields a family similarly complete for VBP.

Updated the section on monotone projection lower bound to include the result that Clique itself is not a monotone p-projection of the Permanent. Also, we describe an explicit construction of rigid and incomparable graphs that can be used in hardness proofs in the paper.

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 $\text{Mod}_pP \not\subseteq P/\text{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. A
simple restriction yields a family similarly complete for VBP.