Some complete and intermediate polynomials in algebraic complexity theory

DOI10.1007/S00224-016-9740-YMaRDI QIDQ6827441zbMATH OpenFDO

Authors Meena Mahajan, Nitin Saurabh

Publication date 1 June 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00224-016-9740-Y

zbMATH Keywords

completenessextension complexityhomomorphismslower boundsmonotone projectionstree decompositionVBPVNP-intermediateVP

Mathematics Subject Classification ID

Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.) (13P25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Cited in

(2)

• Variants of the determinant polynomial and VP-completeness
• Monotone bounded-depth complexity of homomorphism polynomials

This page was built for publication: Some complete and intermediate polynomials in algebraic complexity theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6827441)