Towards an algebraic natural proofs barrier via polynomial identity testing
From MaRDI portal
Publication:6281640
Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)
Abstract: We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich natural proofs barrier in Boolean circuit complexity, in that we rule out a large class of lower bound techniques under a derandomization assumption. We also discuss connections between this algebraic natural proofs barrier, geometric complexity theory, and (algebraic) proof complexity.
This page was built for publication: Towards an algebraic natural proofs barrier via polynomial identity testing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6281640)
