Polymorphisms and Circuit Complexity
classification
💻 cs.CC
keywords
complexitycircuitpolymorphismscharacterizedtabletruthanalyzingboolean
read the original abstract
We present a framework for studying circuit complexity that is inspired by techniques that are used for analyzing the complexity of CSPs. We prove that the circuit complexity of a Boolean function $f$ is characterized by the partial polymorphisms of $f$'s truth table. Moreover, the non-deterministic circuit complexity of $f$ is characterized by the polymorphisms of $f$'s truth table.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.