2026-07-23T04:50:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12571 2024-03-06T10:50:28Z ddc:004 open_access

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem Göös, Mika Kamath, Pritish Sotiraki, Katerina Zampetakis, Manolis Total NP Search Problems Modulo-q arguments Chevalley - Warning Theorem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mika Göös and Pritish Kamath and Katerina Sotiraki and Manolis Zampetakis 2020 Is Part Of LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2020.19 urn:nbn:de:0030-drops-125712 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.19 eng https://creativecommons.org/licenses/by/3.0/legalcode