Guest column: A panorama of counting problems the decision version of which is in P3
Abstract
Since Valiant's seminal work, where the complexity class #P was defined, much research has been done on counting complexity, from various perspectives. A question that permeates many of these efforts concerns the approximability of counting problems, in particular which of them admit an efficient approximation scheme (fpras). A counting problem (a function from Σ* to N) that admits an fpras must necessarily have an easy way to decide whether the output value is nonzero. Having this in mind, we focus our attention on classes of counting problems, the decision version of which is in P (or in RP). We discuss structural characterizations for classes of such problems under various lenses: Cook and Karp reductions, path counting in non-deterministic Turing machines, approximability and approximation-preserving reductions, easy decision by randomization, descriptive complexity, and interval-size functions. We end up with a rich landscape inside #P, revealing a number of inclusions and separations among complexity classes of easy-to-decide counting problems.
References
[1]
Eric Allender and Mitsunori Ogihara. Relationships among PL, #L, and the determinant. RAIRO Theoretical Informatics and Applications, 30(1):1--21, 1996.
[2]
Carme Àlvarez and Birgit Jenner. A very hard log-space counting class. Theoretical Computer Science, 107(1):3--30, 1993.
[3]
Antonis Antonopoulos, Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis, Petros Pantavos, and Stathis Zachos. Completeness, approximability and exponential time results for counting problems with easy decision version. Theoretical Computer Science, 915:55--73, 2022.
[4]
Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram, and Cristian Riveros. Efficient logspace classes for enumeration, counting, and uniform generation. SIGMOD Record, 49(1):52--59, 2020.
[5]
Marcelo Arenas, Martin Muñoz, and Cristian Riveros. Descriptive complexity for counting complexity classes. Logical Methods in Computer Science, 16(1), 2020.
[6]
Eleni Bakali. On properties of counting functions with easy decision version: completeness, approximability, Markov chains, phase transitions. PhD thesis, National Technical University of Athens, Greece, 2018.
[7]
Eleni Bakali, Aggeliki Chalki, and Aris Pagourtzis. Characterizations and approximability of hard counting classes below #P. In Proc. of TAMC 2020, volume 12337 of Lecture Notes in Computer Science, pages 251--262. Springer, 2020.
[8]
Evangelos Bampas, Andreas-Nikolas Göbel, Aris Pagourtzis, and Aris Tentes. On the connection between interval size functions and path counting. Computational Complexity, 26(2):421--467, 2017.
[9]
Alexander I. Barvinok. Combinatorics and Complexity of Partition Functions, volume 30 of Algorithms and combinatorics. Springer, 2016.
[10]
Magnus Bordewich. On the approximation complexity hierarchy. In Proc. of WAOA 2010, volume 6534 of Lecture Notes in Computer Science, pages 37--46. Springer, 2010.
[11]
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, and Eric Vigoda. #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. Journal of Computer and System Sciences, 82(5):690--711, 2016.
[12]
Jin-Yi Cai and Tianyu Liu. Counting perfect matchings and the eight-vertex model. In Proc. of ICALP 2020, volume 168 of LIPIcs, pages 23:1--23:18, 2020.
[13]
Aggeliki Chalki. Structural and descriptive complexity of easy-to-decide counting problems. PhD thesis, National Technical University of Athens, Greece, 2022.
[14]
Angeliki Chalki. Counting below #P: Classes, problems and descriptive complexity. Master's thesis, National and Kapodistrian University of Athens, Greece, 2016.
[15]
Nilesh N. Dalvi and Dan Suciu. The dichotomy of probabilistic inference for unions of conjunctive queries. Journal of the ACM, 59(6):30:1--30:87, 2012.
[16]
Cassio P. de Campos, Georgios Stamoulis, and Dennis Weyland. A structured view on weighted counting with relations to counting, quantum computation and applications. Information and Computation, 275:104627, 2020.
[17]
Manfred Droste and Paul Gastin. Weighted automata and weighted logics. Theoretical Computer Science, 380(1-2):69--86, 2007.
[18]
Arnaud Durand, Miki Hermann, and Phokion G. Kolaitis. Subtractive reductions and complete problems for counting complexity classes. Theoretical Computer Science, 340(3):496--513, 2005.
[19]
Martin E. Dyer, Alan M. Frieze, and Ravi Kannan. A random polynomial time algorithm for approximating the volume of convex bodies. Journal of the ACM, 38(1):1--17, 1991.
[20]
Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38(3):471--500, 2004.
[21]
Martin E. Dyer, Leslie Ann Goldberg, and Mark Jerrum. An approximation trichotomy for Boolean #CSP. Journal of Computer and System Sciences, 76(3-4):267--277, 2010.
[22]
Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. SIAM-AMS Proceedings, 7:43--73, 1974.
[23]
Piotr Faliszewski and Lane A. Hemaspaandra. The complexity of power-index comparison. Theoretical Computer Science, 410(1):101--107, 2009.
[24]
Stephen A. Fenner, Lance Fortnow, and Stuart A. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48(1):116--148, 1994.
[25]
Sophie Fischer, Lane A. Hemaspaandra, and Leen Torenvliet. Witness-isomorphic reductions and the local search problem (extended abstract). In Proc. of MFCS 1995, volume 969 of Lecture Notes in Computer Science, pages 277--287. Springer, 1995.
[26]
Tobias Friedrich, Andreas Göbel, Martin S. Krejca, and Marcus Pappik. A spectral independence view on hard spheres via block dynamics. In Proc. of ICALP 2021, volume 198 of LIPIcs, pages 66:1--66:15, 2021.
[27]
Andreas Galanis, Qi Ge, Daniel Stefankovic, Eric Vigoda, and Linji Yang. Improved inapproximability results for counting independent sets in the hard-core model. Random Structures & Algorithms, 45(1):78--110, 2014.
[28]
Leslie Ann Goldberg. Efficient algorithms for listing combinatorial structures. PhD thesis, University of Edinburgh, UK, 1991.
[29]
Leslie Ann Goldberg and Mark Jerrum. Approximating the partition function of the ferromagnetic Potts model. Journal of the ACM, 59(5):25:1--25:31, 2012.
[30]
Leslie Ann Goldberg and Mark Jerrum. The complexity of computing the sign of the Tutte polynomial. SIAM Journal on Computing, 43(6):1921--1952, 2014.
[31]
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
[32]
Vivek Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk, and Stephen R. Mahaney. A quasi-polynomial-time algorithm for sampling words from a context-free language. Information and Computation, 134(1):59--74, 1997.
[33]
Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang. Zeros of holant problems: Locations and algorithms. ACM Transactions on Algorithms, 17(1):4:1--4:25, 2021.
[34]
Lane A. Hemaspaandra, Christopher M. Homan, Sven Kosub, and Klaus W. Wagner. The complexity of computing the size of an interval. SIAM Journal on Computing, 36(5):1264--1300, 2007.
[35]
Lane A. Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2002.
[36]
Lane A. Hemaspaandra and Heribert Vollmer. The satanic notations: Counting classes beyond #P and other definitional adventures. SIGACT News, 26(1):2--13, March 1995.
[37]
Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999.
[38]
Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM, 51(4):671--697, July 2004.
[39]
Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169--188, 1986.
[40]
David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119--123, 1988.
[41]
Sampath Kannan, Z. Sweedyk, and Stephen R. Mahaney. Counting and random generation of strings in regular languages. In Proc. of SODA 1995, pages 551--557. ACM/SIAM, 1995.
[42]
David R Karger. A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM Review, 43(3):499--522, 2001.
[43]
Richard M Karp, Michael Luby, and Neal Madras. Monte-Carlo approximation algorithms for enumeration problems. Journal of Algorithms, 10(3):429--448, 1989.
[44]
Pieter W Kasteleyn. Dimer statistics and phase transitions. Journal of Mathematical Physics, 4(2):287--293, 1963.
[45]
Aggelos Kiayias, Aris Pagourtzis, Kiron Sharma, and Stathis Zachos. Acceptor-definable counting classes. In Proc. of PCI 2001, volume 2563 of Lecture Notes in Computer Science, pages 453--463, 2001.
[46]
Gustav Kirchhoff. Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Annalen der Physik, 148(12):497--508, 1847.
[47]
D. Knuth. Estimating the efficiency of backtrack programs. Mathematics of Computation, 29:122--136, 1974.
[48]
Johannes Köbler, Uwe Schöning, and Jacobo Torán. On counting and approximation. Acta Informatica, 26(4):363--379, 1989.
[49]
Mark W Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 36(3):490--509, 1988.
[50]
Jingcheng Liu and Pinyan Lu. FPTAS for counting monotone CNF. In Proc. of SODA 2015, pages 1531--1548. SIAM, 2015.
[51]
Noam Livne. A note on #P-completeness of NP-witnessing relations. Information Processing Letters, 109(5):259--261, 2009.
[52]
Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6):1087--1092, 1953.
[53]
Mitsunori Ogiwara and Lane A. Hemachandra. A complexity theory for feasible closure properties. Journal of Computer and System Sciences, 46(3):295--325, 1993.
[54]
Aris Pagourtzis. On the complexity of hard counting problems with easy decision version. In Proc. of PLS 2001, Panhellenic Logic Symposium, 2001.
[55]
Aris Pagourtzis and Stathis Zachos. The complexity of counting functions with easy decision version. In Proc. of MFCS 2006, volume 4162 of Lecture Notes in Computer Science, pages 741--752, 2006.
[56]
Viresh Patel and Guus Regts. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM Journal on Computing, 46(6):1893--1919, 2017.
[57]
Sanjeev Saluja, K.V. Subrahmanyam, and Madhukar N. Thakur. Descriptive complexity of #P functions. Journal of Computer and System Sciences, 50(3):493--505, 1995.
[58]
Abraham Sharell. Descriptive complexity and approximation of counting functions. PhD thesis, Université Paris 11, Orsay (France), February 1998.
[59]
Yongtang Shi, Matthias Dehmer, Xueliang Li, and Ivan Gutman. Graph polynomials. CRC Press, 2016.
[60]
Janos Simon. On some central problems in computational complexity. PhD thesis, Cornell University, USA, 1975.
[61]
Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation, 82(1):93--133, 1989.
[62]
Allan Sly. Computational transition at the uniqueness threshold. In Proc. of FOCS 2010, pages 287--296. IEEE Computer Society, 2010.
[63]
Richard Szeliski. Computer vision: algorithms and applications. Springer Science & Business Media, 2010.
[64]
Harold NV Temperley and Michael E Fisher. Dimer problem in statistical mechanics - an exact result. Philosophical Magazine, 6(68):1061--1063, 1961.
[65]
Seinosuke Toda. On the computational power of PP and ⊕. In Proc. of FOCS 1989, pages 514--519. IEEE Computer Society, 1989.
[66]
Seinosuke Toda. PP is as hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing, 20(5):865--877, 1991.
[67]
Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189--201, 1979.
[68]
Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410--421, 1979.
[69]
Heribert Vollmer. On different reducibility notions for function classes. In Proc. of STACS 94, volume 775 of Lecture Notes in Computer Science, pages 449--460. Springer, 1994.
[70]
Dror Weitz. Counting independent sets up to the tree threshold. In Proc. of STOC 2006, pages 140--149. ACM, 2006.
[71]
Viktória Zankó. #P-completeness via many-one reductions. International Journal of Foundations of Computer Science, 02(01):77--82, 1991.
[72]
David Zuckerman. On unapproximable versions of NP-complete problems. SIAM Journal on Computing, 25(6):1293--1304, December 1996.
- Guest column: A panorama of counting problems the decision version of which is in P3
Recommendations
Completeness, approximability and exponential time results for counting problems with easy decision version
Highlights- The first TotP-complete problems under parsimonious reductions.
- Hardness of ...
AbstractHard counting problems with easy decision version, like computing the permanent and counting independent sets, are of particular importance in counting complexity theory. TotP is the class of all self-reducible problems in # P with ...
Guest column: inapproximability results via Long Code based PCPs
Summer has come again. And what better way is there to spend a summer than to relax on a sandy beach, on a mountain top, or at a park's picnic tables, and... think theory! Summer is a particularly good time to attack the big questions whose openness ...
The Complexity of Planar Counting Problems
We prove the #P-hardness of the counting problems associated with various satisfiability, graph, and combinatorial problems, when restricted to planar instances. These problems include 3Sat, 1-3Sat, 1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set,...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2022
66 pages
Copyright © 2022 Copyright is held by the owner/author(s).
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 August 2022
Published in SIGACT Volume 53, Issue 3
Check for updates
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 77Total Downloads
- Downloads (Last 12 months)21
- Downloads (Last 6 weeks)2
Reflects downloads up to 26 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in