Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity

Опубликовано 6 сентября 2016, 6:23

Cohomology, in particular counting Betti numbers, was a known technique in algebraic complexity theory in the late 1970's and early 1980's. Speculation arose as to whether such methods could attack lower bounds in Boolean complexity theory (e.g., P vs. NP), by modeling Boolean functions with topological objects. We shall show that if one generalizes the setting to Grothendieck topologies, it may be possible to circumvent two obstacles to connecting Boolean depth complexity lower bounds to cohomology. We describe ongoing research to look for models of Grothendieck topologies that yield, via these techniques, interesting lower bounds. As a simple example, we show that if we consider circuits with only AND gates, which is essentially a SET COVER problem, using a free category and injectives sheaves (i.e., an extremely special and simple situation) we can rederive the relaxed LP bound. For the talk we do not assume prior knowledge of complexity theory or Grothendieck topologies.