Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity II: A Simple Example
- Postscript version.
- Dvi version.
- PDF version.
In a previous paper we have suggested a number of ideas to attack
circuit size complexity with cohomology. As a simple example,
we take circuits that can only compute the AND of two inputs,
which essentially reduces to SET COVER. We show a very special
case of the cohomological approach (one particular free category,
using injective and superskyscraper sheaves) gives the linear
programming bound coming from the relaxation of the standard integer
programming reformulation of SET COVER.