Book contents
- Frontmatter
- Contents
- Preface
- List of Participants
- Relationships Between Monotone and Non-Monotone Network Complexity
- On Read-Once Boolean Functions
- Boolean Function Complexity: a Lattice-Theoretic Perspective
- Monotone Complexity
- On Submodular Complexity Measures
- Why is Boolean Complexity Theory so Difficult?
- The Multiplicative Complexity of Boolean Quadratic Forms, a Survey
- Some Problems Involving Razborov-Smolensky Polynomials
- Symmetry Functions in AC° can be Computed in Constant Depth with Very Small Size
- Boolean Complexity and Probabilistic Constructions
- Networks Computing Boolean Functions for Multiple Input Values
- Optimal Carry Save Networks
Why is Boolean Complexity Theory so Difficult?
Published online by Cambridge University Press: 23 September 2009
- Frontmatter
- Contents
- Preface
- List of Participants
- Relationships Between Monotone and Non-Monotone Network Complexity
- On Read-Once Boolean Functions
- Boolean Function Complexity: a Lattice-Theoretic Perspective
- Monotone Complexity
- On Submodular Complexity Measures
- Why is Boolean Complexity Theory so Difficult?
- The Multiplicative Complexity of Boolean Quadratic Forms, a Survey
- Some Problems Involving Razborov-Smolensky Polynomials
- Symmetry Functions in AC° can be Computed in Constant Depth with Very Small Size
- Boolean Complexity and Probabilistic Constructions
- Networks Computing Boolean Functions for Multiple Input Values
- Optimal Carry Save Networks
Summary
Introduction
In the last decade substantial progress has been made in our understanding of restricted classes of Boolean circuits, in particular those restricted to have constant depth (Furst, Sipser, Saxe, Ajtai, Yao, Haiåstad, Razborov, Smolensky or to be monotone (Razborov, Andreev, Alon and Boppana, Tardos, Karchmer and Wigderson). The question arises, perhaps more urgently than before, as to what approaches could be pursued that might contribute to progress on the unrestricted model.
In this note we first argue that if P ≠ NP then any circuit-theoretic proof of this would have to be preceded by analogous results for the more constrained arithmetic model. This is because, as we shall observe, there are proven implications showing that if, for example, the Hamiltonian cycle problem (HC) requires exponential circuit size, then so does the analogous problem on arithmetic circuits. Since the set of valid algebraic identities in the latter model form a proper subset of those in the former, a lower bound proof for it should be strictly easier.
In spite of the above relationship the algebraic model is often regarded as an alternative, rather than a restriction of the Boolean model. One reason for this is that specific computations are usually understandable in one of these models, and not in both. In particular, the main power of the algebraic model derives from the possibility of cancellations, and it is usually difficult to express explicitly how these help in computing combinatorial problems.
- Type
- Chapter
- Information
- Boolean Function Complexity , pp. 84 - 94Publisher: Cambridge University PressPrint publication year: 1992
- 41
- Cited by