Boolean formulae, hypergraphs and combinatorial topology (Q712196)

The authors introduce the theta complex \(\Theta(\mathcal H)\) associated to a hypergraph \(\mathcal H\), which is the Alexander dual of the independence complex of \(\mathcal H\). The motivation for this construction comes from the study of decision problems and the P/NP question of computer science. One can associate to a set of Boolean formulae a simplicial complex. In particular, the authors show that \(| k-\text{SAT}-n|\), the simplicial complex associated to satisfiable formulae in \(k\)-conjunctive normal form with at most \(n\) variables, is homotopically equivalent to \(\Theta\bigl(\text{Cube}(n,n-k)\bigr)\) where \(\text{Cube}(n,l)\) is the hypergraph whose vertices are the vertices of an \(n\)-cube, and whose hyperedges are given by the \(l\)-dimensional faces of the \(n\)-cube. As it is known that 2-SAT is a P problem and \(k\)-SAT is an NP complete problem for \(k\geq 3\), there is the hope that the topology of the theta complexes gives a way to understand the P/NP question by studying the difference between 2-SAT and \(k\)-SAT (for \(k\geq 3\)). More precisely, the authors conjecture that \(\Theta\bigl(\text{Cube}(n,n-2)\bigr)\) has the homotopy type of a wedge of \((2n-2)\)-dimensional spheres (conjecture 1) and that, for \(3\leq k< n\) (and \(n\) sufficiently large), \(\Theta\bigl(\text{Cube}(n,n-k)\bigr)\) is not homotopy equivalent to a wedge of same-dimensional spheres (conjecture 2). By studying group actions on hypergraphs, the authors get results about the Euler characteristic of \(\Theta\bigl(\text{Cube}(n,n-2)\bigr)\) modulo \(p\) (for all prime \(p\leq n\)) which are consistent with conjecture 1. These questions give a strong motivation to study the homotopy type of theta complexes of hypergraphs and the paper is also devoted to the study of this construction on its own. A complete characterization of the homotopy type of \(\Theta(\mathcal H)\) is given for certain graphs (paths and cycles) or certain polyhedra. The homotopy type of \(\Theta\bigl(\text{Cube}(n,l)\bigr)\) is calculated in various cases and some results are obtained by use of computer. In all these calculations, the main tool is the discrete Morse theory (and the use of sequential vector fields for reducing the number of critical cells).