文章基本信息
- 标题：Closure of VP under taking factors: a short and simple proof
- 本地全文：下载
- 作者：Chi-Ning Chou ; Mrinal Kumar ; Noam Solomon 等
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2019
- 卷号：2019
- 页码：1-10
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree d polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can be computed by an arithmetic circuit of size at most poly(s, n, d).
However, unlike Kaltofen's argument, our proof does not directly give an efficient algorithm for computing the circuits for the factors of f.
