Résumé
The computational cost of counting the number of solutions satisfying a Boolean formula, which is a problem instance of #SAT, has proven subtle to quantify. Even when finding individual satisfying solutions is computationally easy (e.g. 2-SAT, which is in $$\mathsf{{P}}$$P), determining the number of solutions can be #$$\mathsf{{P}}$$P-hard. Recently, computational methods simulating quantum systems experienced advancements due to the development of tensor network algorithms and associated quantum physics-inspired techniques. By these methods, we give an algorithm using an axiomatic tensor contraction language for n-variable #SAT instances with complexity $$O((g+cd)^{O(1)} 2^c)$$O((g+cd)O(1) 2c) where c is the number of COPY-tensors, g is the number of gates, and d is the maximal degree of any COPY-tensor. Thus, n-variable counting problems can be solved efficiently when their tensor network expression has at most $$O(\log n)$$O(logn) COPY-tensors and polynomial fan-out. This framework also admits an intuitive proof of a variant of the Tovey conjecture (the r,1-SAT instance of the Dubois–Tovey theorem). This study increases the theory, expressiveness and application of tensor based algorithmic tools and provides an alternative insight on these problems which have a long history in statistical physics and computer science.
| Langue originale | Anglais |
|---|---|
| Pages (de - à) | 1389-1404 |
| Nombre de pages | 16 |
| Revue | Journal of Statistical Physics |
| Volume | 160 |
| Numéro de publication | 5 |
| Les DOIs | |
| État | Publié - 1 sept. 2015 |
| Modification externe | Oui |
Classification disciplinaire ASJC Scopus
- Physique statistique et non linéaire
- Physique mathématique
- Physique de la matière condensée
- Mathématiques appliquées
Empreinte digitale
Voici les principaux termes ou expressions associés à « Tensor Network Contractions for #SAT ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.Citer cette ressource
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver