Monomials in arithmetic circuits: Complete problems in the counting hierarchy

Autor: Stefan Mengel, Guillaume Malod, Hervé Fournier
Přispěvatelé: Dürr, Christoph, Christoph Dürr, Thomas Wilke, Parallélisme, Réseaux, Systèmes, Modélisation (PRISM), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Centre National de la Recherche Scientifique (CNRS)
Jazyk: angličtina
Rok vydání: 2012
Předmět:
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
FOS: Computer and information sciences
Monomial
Multilinear map
counting problems
Arithmetic circuits
polynomials
General Mathematics
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
MathematicsofComputing_GENERAL
[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Disjoint sets
0102 computer and information sciences
Computational Complexity (cs.CC)
01 natural sciences
Theoretical Computer Science
Computer Science::Emerging Technologies
arithmetic circuits
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
Arithmetic circuit complexity
0101 mathematics
Mathematics
Discrete mathematics
000 Computer science
knowledge
general works
Hierarchy (mathematics)
010102 general mathematics
Univariate
Algebra
Computer Science - Computational Complexity
Computational Mathematics
Computational Theory and Mathematics
Counting problem
010201 computation theory & mathematics
Computer Science
[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC]
F.1.3
Zdroj: Symposium on Theoretical Aspects of Computer Science
STACS'12 (29th Symposium on Theoretical Aspects of Computer Science)
STACS'12 (29th Symposium on Theoretical Aspects of Computer Science), Feb 2012, Paris, France. pp.362-373
DOI: 10.4230/lipics.stacs.2012.362
Popis: We consider the complexity of two questions on polynomials given by arithmetic circuits: testing whether a monomial is present and counting the number of monomials. We show that these problems are complete for subclasses of the counting hierarchy which had few or no known natural complete problems before. We also study these questions for circuits computing multilinear polynomials and for univariate multiplicatively disjoint circuits.
Databáze: OpenAIRE
Externí odkaz: