Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR16-038 | 21st November 2016 22:43

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

RSS-Feed




Revision #2
Authors: Meena Mahajan, Nitin Saurabh
Accepted on: 21st November 2016 22:43
Downloads: 864
Keywords: 


Abstract:

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.



Changes to previous version:

Added a VNP-complete family of homomorphism polynomials


Revision #1 to TR16-038 | 23rd July 2016 05:28

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory





Revision #1
Authors: Meena Mahajan, Nitin Saurabh
Accepted on: 23rd July 2016 05:29
Downloads: 836
Keywords: 


Abstract:

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.



Changes to previous version:

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.


Paper:

TR16-038 | 15th March 2016 09:24

Some Complete and Intermediate Polynomials in Algebraic Complexity Theory





TR16-038
Authors: Meena Mahajan, Nitin Saurabh
Publication: 15th March 2016 15:04
Downloads: 1343
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint