Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

Abstract

We provide a list of new natural V N P-intermediate polynomial families, based on basic (combinatorial) N P-complete problems that are complete under parsimonious reductions. Over finite fields, these families are in V N P, and under the plausible hypothesis M o d p P ⫅̸ P / p o l y, are neither V N P-hard (even under oracle-circuit reductions) nor in V P. Prior to this, only the Cut Enumerator polynomial was known to be V N P-intermediate, as shown by Bürgisser in 2000. We show next 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 V P-complete under polynomial-size projections. This complements a recent result of Durand et al. (2014) which established V P-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 V B P.