On the relative power of reduction notions in arithmetic circuit complexity

DOI10.1016/J.IPL.2017.09.009zbMATH Open1419.68054arXiv1609.05942OpenAlexW2521537240MaRDI QIDQ1679901FDOQ1679901

Authors: Christian Ikenmeyer, Stefan Mengel 

Publication date: 22 November 2017

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

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.

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

Recommendations

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

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)

Cites Work

• Negation can be exponentially powerful
• Completeness and reduction in algebraic complexity theory
• Separation of NP-completeness notions
• A dichotomy theorem for homomorphism polynomials
• Title not available (Why is that?)
• The complexity theory companion
• Algebraic complexity classes
• Homomorphism polynomials complete for VP
• A Dichotomy Theorem for Polynomial Evaluation

Cited In (9)

• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on VNP-completeness and border complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)