On the relative power of reduction notions in arithmetic circuit complexity

DOI10.1016/J.IPL.2017.09.009MaRDI QIDQ1679901zbMATH OpenOpenAlexFDO

Authors Christian Ikenmeyer, Stefan Mengel

Publication date 22 November 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.05942

zbMATH Keywords

computational complexityarithmetic circuitsreductionstheory of computationp-projectionc-reductionHamiltonian cycle polynomial

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 3936520
• Constant Depth Reducibility
• Completeness and reduction in algebraic complexity theory

Cites work

• scientific article; zbMATH DE number 3744549 (Why is no real title available?)
• A Dichotomy Theorem for Polynomial Evaluation
• A dichotomy theorem for homomorphism polynomials
• Algebraic complexity classes
• Completeness and reduction in algebraic complexity theory
• Homomorphism polynomials complete for VP
• Negation can be exponentially powerful
• Separation of NP-completeness notions
• The complexity theory companion

Cited in

(9)

• scientific article; zbMATH DE number 7561742 (Why is no real title available?)
• scientific article; zbMATH DE number 1722667 (Why is no real title available?)
• A note on VNP-completeness and border complexity
• scientific article; zbMATH DE number 3936520 (Why is no real title available?)
• scientific article; zbMATH DE number 4182020 (Why is no real title available?)
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• On the power of deterministic reductions to C=P
• Modified Redundant Representation for Designing Arithmetic Circuits with Small Complexity
• Schur polynomials do not have small formulas if the determinant does not

This page was built for publication: On the relative power of reduction notions in arithmetic circuit complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679901)