文章基本信息

标题：On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem
本地全文：下载
作者：Mika G{"o}{"o}s ; Pritish Kamath ; Katerina Sotiraki 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：169
页码：19:1-19:42
DOI：10.4230/LIPIcs.CCC.2020.19
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the search problem class PPA_q 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 PPA_p 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 PPA_p 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 PPA_p 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 PPA_q.
关键词：Total NP Search Problems; Modulo-q arguments; Chevalley - Warning Theorem