On the complexity of modulo-q arguments and the chevalley-warning theorem
On the complexity of modulo-q arguments and the chevalley-warning theorem
复制标题
关于模 q 参数的复杂性和谢瓦利警告定理
DOI：
10.4230/lipics.ccc.2020.19
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Manolis Zampetakis
中科院分区：
文献类型：
--
作者：
Mika Göös;Pritish Kamath;Katerina Sotiraki;Manolis Zampetakis
我们研究搜索问题类 PPAq，它被定义为 Papadimitriou (JCSS 1994) 引入的著名多项式奇偶校验参数类 PPA 的模 q 模拟。我们的第一个结果表明，此类可以用素数 p 的 PPAp 来表征。我们的主要结果是确定与 Chevalley-Warning 定理相关的搜索问题的显式版本对于素数 p 的 PPAp 是完整的。这个问题很自然，因为它没有明确地将电路作为输入的一部分。当 p ≥ 3 时，这是 PPAp 的第一个完整问题。最后，我们讨论 Chevalley-Warning 定理和经过充分研究的短整数解问题之间的联系，并调查 PPAq 的结构特性。
We study the search problem class PPAq defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPAp for prime p. Our main result is to establish that an explicit version of a search problem associated to the Chevalley-Warning theorem is complete for PPAp for prime p. This problem is natural in that it does not explicitly involve circuits as part of the input. It is the first such complete problem for PPAp when p ≥ 3. Finally we discuss connections between Chevalley-Warning theorem and the well-studied short integer solution problem and survey the structural properties of PPAq.