 |
Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity
- Postscript version.
- Dvi version.
- PDF version.
-
Abstract:
This paper is motivated by questions such as P vs. NP and
other questions in Boolean complexity theory.
We describe an approach to attacking such questions
with cohomology, and we show that using Grothendieck topologies
and other ideas from the Grothendieck school gives new hope for
such an attack.
We focus on circuit depth complexity, and
consider only finite topological spaces or Grothendieck
topologies based on finite categories; as such, we do not
use algebraic geometry or manifolds.
Given two sheaves on a Grothendieck topology, their
cohomological complexity is the sum of the dimensions of
their Ext groups.
We seek to model the depth complexity of Boolean
functions by the cohomological complexity of
sheaves on a Grothendieck topology.
We propose that the logical AND of two Boolean functions
will have its corresponding cohomological complexity
bounded in terms of those of the two functions
using ``virtual zero extensions.''
We propose that the logical
negation of a function
will have its corresponding cohomological complexity
equal to that of the original function using duality theory.
We explain these approaches and show that they are stable under
pullbacks and base change.
It is the subject of
ongoing work to achieve AND and negation bounds simultaneously in a
way that yields an interesting depth lower bound.
|