Revision #2 Authors: Meena Mahajan, Nitin Saurabh

Accepted on: 21st November 2016 22:43

Downloads: 84

Keywords:

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

Revision #1 Authors: Meena Mahajan, Nitin Saurabh

Accepted on: 23rd July 2016 05:29

Downloads: 122

Keywords:

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.

TR16-038 Authors: Meena Mahajan, Nitin Saurabh

Publication: 15th March 2016 15:04

Downloads: 357

Keywords:

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.