ECCC-Report TR16-038https://eccc.weizmann.ac.il/report/2016/038Comments and Revisions published for TR16-038en-usMon, 21 Nov 2016 22:43:23 +0200
Revision 2
| Some Complete and Intermediate Polynomials in Algebraic Complexity Theory |
Meena Mahajan,
Nitin Saurabh
https://eccc.weizmann.ac.il/report/2016/038#revision2We 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.Mon, 21 Nov 2016 22:43:23 +0200https://eccc.weizmann.ac.il/report/2016/038#revision2
Revision 1
| Some Complete and Intermediate Polynomials in Algebraic Complexity Theory |
Meena Mahajan,
Nitin Saurabh
https://eccc.weizmann.ac.il/report/2016/038#revision1We 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.Sat, 23 Jul 2016 05:29:00 +0300https://eccc.weizmann.ac.il/report/2016/038#revision1
Paper TR16-038
| Some Complete and Intermediate Polynomials in Algebraic Complexity Theory |
Meena Mahajan,
Nitin Saurabh
https://eccc.weizmann.ac.il/report/2016/038We 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.Tue, 15 Mar 2016 15:04:40 +0200https://eccc.weizmann.ac.il/report/2016/038