文章基本信息

标题：Monomials in arithmetic circuits: Complete problems in the counting hierarchy
本地全文：下载
作者：Herv{\'e} Fournier ; Guillaume Malod ; Stefan Mengel 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：14
页码：362-373
DOI：10.4230/LIPIcs.STACS.2012.362
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：arithmetic circuits; counting problems; polynomials