Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity II: A Simple Example

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
8 pages

Keywords

Computational Complexity, Algebraic Geometry

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/111024

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0604024
 http://arxiv.org/abs/cs/0604024

Collections

arXiv