2016/09/19 by Christian Ikenmeyer, Stefan Mengel, Ikenmeyer, Christian +1
Computer Science · #68Q15 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #acm:68Q15 #cs.CC #msc:68Q15 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1609.05942
arxiv created 2016/09/19 · openalex publication_date 2016/09/19 · arxiv updated 2016/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the two main reduction notions in arithmetic circuit complexity, p-projections and c-reductions, differ in power. We do so by showing unconditionally that there are polynomials that are VNP-complete under c-reductions but not under p-projections. We also show that the question of which polynomials are VNP-complete under which type of reductions depends on the underlying field.