×

On the connection between interval size functions and path counting. (English) Zbl 1401.68107

Summary: We investigate the complexity of hard (#P-complete) counting problems that have easy decision version. By “easy decision,” we mean that deciding whether the result of counting is nonzero is in P. This property is shared by several well-known problems, such as counting the number of perfect matchings in a given graph or counting the number of satisfying assignments of a given DNF formula. We focus on classes of such hard-to-count easy-to-decide problems which emerged through two seemingly disparate approaches: one taken by L. A. Hemaspaandra et al. [SIAM J. Comput. 36, No. 5, 1264–1300 (2006; Zbl 1123.68041)], who defined classes of functions that count the size of intervals of ordered strings, and one followed by A. Kiayias et al. [Lect. Notes Comput. Sci. 2563, 453–463 (2003; Zbl 1026.68566)], who defined the class TotP, consisting of functions that count the total number of paths of NP computations. We provide inclusion and separation relations between TotP and interval size counting classes, by means of new classes that we define in this work. Our results imply that many known #P-complete problems with easy decision are contained in the classes defined by Hemaspaandra et al., but are unlikely to be complete for these classes under reductions under which these classes are downward closed, e.g., parsimonious reductions. This, applied to the #MonSat problem, partially answers an open question of Hemaspaandra et al. We also define a new class of interval size functions which strictly contains FP and is strictly contained in TotP under reasonable complexity-theoretic assumptions. We show that this new class contains hard counting problems.

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Àlvarez Carme, Birgit Jenner (1993) A very hard log-space counting class. Theoretical Computer Science 107(1): 3-30 · Zbl 0813.68098 · doi:10.1016/0304-3975(93)90252-O
[2] Evangelos Bampas, Andreas-Nikolas Göbel, Aris Pagourtzis & Aris Tentes (2009). On the connection between interval size functions and path counting. In Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation, volume 5532 of Lecture Notes in Computer Science, 108-117. · Zbl 1241.68067
[3] Dyer Martin E., Leslie Ann Goldberg, Greenhill Catherine S., Mark Jerrum (2003) The relative complexity of approximate counting problems. Algorithmica 38(3): 471-500 · Zbl 1138.68424 · doi:10.1007/s00453-003-1073-y
[4] Hemaspaandra Lane A., Homan Christopher M., Sven Kosub, Wagner Klaus W. (2007) The complexity of computing the size of an interval. SIAM Journal on Computing 36(5): 1264-1300 · Zbl 1123.68041 · doi:10.1137/S0097539705447013
[5] Lane A. Hemaspaandra & Mitsunori Ogihara (2002). The Complexity Theory Companion. Springer-Verlag Berlin Heidelberg. · Zbl 0993.68042
[6] Hempel Harald, Wechsung Gerd (2000) The operators min and max on the polynomial hierarchy. International Journal of Foundations of Computer Science 11(2): 315-342 · Zbl 1319.68095 · doi:10.1142/S0129054100000181
[7] Jerrum Mark, Sinclair Alistair, Vigoda Eric (2004) A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM 51(4): 671-697 · Zbl 1204.65044 · doi:10.1145/1008731.1008738
[8] Karp Richard M., Luby Michael, Madras Neal (1989) Monte-Carlo approximation algorithms for enumeration problems. Journal of Algorithms 10(3): 429-448 · Zbl 0678.65001 · doi:10.1016/0196-6774(89)90038-2
[9] Aggelos Kiayias, Aris Pagourtzis, Kiron Sharma & Stathis Zachos (2001). Acceptor-definable counting classes. In Proceedings of the 8th Panhellenic Conference on Informatics, Revised Selected Papers, volume 2563 of Lecture Notes in Computer Science, 453-463. · Zbl 1026.68566
[10] Jingcheng Liu, Pinyan Lu & Chihao Zhang (2014). FPTAS for counting weighted edge covers. In Proceedings of the 22nd Annual European Symposium on Algorithms, volume 8737 of Lecture Notes in Computer Science, 654-665. · Zbl 1425.68457
[11] Aris Pagourtzis (2001). On the complexity of hard counting problems with easy decision version. In Proceedings of the 3rd Panhellenic Logic Symposium. · Zbl 1132.68425
[12] Aris Pagourtzis & Stathis Zachos (2006). The complexity of counting functions with easy decision version. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, volume 4162 of Lecture Notes in Computer Science, 741-752. · Zbl 1132.68425
[13] Saluja Sanjeev, Subrahmanyam K. V., Thakur Madhukar N. (1995) Descriptive complexity of #P functions. Journal of Computer and System Sciences 50(3): 493-505 · Zbl 0837.68034 · doi:10.1006/jcss.1995.1039
[14] Toda Seinosuke (1991) PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing 20(5): 865-877 · Zbl 0733.68034 · doi:10.1137/0220053
[15] Toda Seinosuke, Osamu Watanabe (1992) Polynomial time 1-Turing reductions from #PH to #P. Theoretical Computer Science 100(1): 205-221 · Zbl 0779.68037 · doi:10.1016/0304-3975(92)90369-Q
[16] Leslie G. Valiant (1979a). The complexity of computing the permanent. Theoretical Computer Science8, 189-201. · Zbl 0415.68008
[17] Leslie G. Valiant (1979b). The complexity of enumeration and reliability problems. SIAM Journal on Computing8(3), 410-421. · Zbl 0419.68082
[18] Dror Weitz (2006). Counting independent sets up to the tree threshold. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 140-149. · Zbl 1301.68276
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.