Boolean formulae, hypergraphs and combinatorial topology
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).
- P/NP , and the quantum field computer
- A user's guide to discrete Morse theory
- Complexes of directed trees
- Complexes of directed trees and independence complexes
- scientific article; zbMATH DE number 1775445 (Why is no real title available?)
- scientific article; zbMATH DE number 2103273 (Why is no real title available?)
- Limit, logic, and computation
- Morse theory for cell complexes
- Simplicial complexes of graphs
- Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
- Relative definability of boolean functions via hypergraphs
- On the capacity of Boolean graph formulæ
- Threshold complexes and connections to number theory
- On the topology of a Boolean representable simplicial complex
- Boolean Structures
- HOMOTOPY MODEL THEORY
- Homology of the Boolean complex
This page was built for publication: Boolean formulae, hypergraphs and combinatorial topology
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q712196)
