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)

zbMATH Keywords

lower boundscompletenesshomomorphismstree decompositionextension complexitymonotone projectionsVBPVNP-intermediateVP

Mathematics Subject Classification ID

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

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)