On the relative power of reduction notions in arithmetic circuit complexity

DOI10.1016/j.ipl.2017.09.009zbMath1419.68054arXiv1609.05942OpenAlexW2521537240MaRDI QIDQ1679901

Stefan Mengel, Christian Ikenmeyer

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 complexityreductionstheory of computationarithmetic circuitsp-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)

Related Items (3)

A note on VNP-completeness and border complexity ⋮ Schur polynomials do not have small formulas if the determinant does not ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Negation can be exponentially powerful
• Completeness and reduction in algebraic complexity theory
• Some complete and intermediate polynomials in algebraic complexity theory
• Separation of NP-Completeness Notions
• Algebraic Complexity Classes
• A Dichotomy Theorem for Homomorphism Polynomials
• Homomorphism Polynomials Complete for VP
• A Dichotomy Theorem for Polynomial Evaluation
• The complexity theory companion

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