{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:18:54Z","timestamp":1760080734781,"version":"3.41.0"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T00:00:00Z","timestamp":1661817600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:p>\n            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 (\n            <jats:italic>fpras<\/jats:italic>\n            ). A counting problem (a function from \u03a3\n            <jats:sup>*<\/jats:sup>\n            to N) that admits an\n            <jats:italic>fpras<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/3561064.3561072","type":"journal-article","created":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T05:45:55Z","timestamp":1661924755000},"page":"46-68","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Guest column: A panorama of counting problems the decision version of which is in P"],"prefix":"10.1145","volume":"53","author":[{"given":"Eleni","family":"Bakali","sequence":"first","affiliation":[{"name":"National Technical University of Athens, Greece"}]},{"given":"Aggeliki","family":"Chalki","sequence":"additional","affiliation":[{"name":"National Technical University of Athens, Greece"}]},{"given":"Andreas","family":"G\u00f6bel","sequence":"additional","affiliation":[{"name":"University of Potsdam, Germany"}]},{"given":"Aris","family":"Pagourtzis","sequence":"additional","affiliation":[{"name":"National Technical University of Athens, Greece"}]},{"given":"Stathis","family":"Zachos","sequence":"additional","affiliation":[{"name":"National Technical University of Athens, Greece"}]}],"member":"320","published-online":{"date-parts":[[2022,8,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1996300100011"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90252-O"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.02.030"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422648.3422661"},{"key":"e_1_2_1_5_1","volume-title":"Descriptive complexity for counting complexity classes. Logical Methods in Computer Science, 16(1)","author":"Arenas Marcelo","year":"2020","unstructured":"Marcelo Arenas, Martin Mu\u00f1oz, and Cristian Riveros. Descriptive complexity for counting complexity classes. Logical Methods in Computer Science, 16(1), 2020."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59267-7_22"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0137-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-51829-9"},{"key":"e_1_2_1_10_1","series-title":"Lecture Notes in Computer Science","first-page":"37","volume-title":"Proc. of WAOA","author":"Bordewich Magnus","year":"2010","unstructured":"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."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.11.009"},{"key":"e_1_2_1_12_1","first-page":"1","volume-title":"Proc. of ICALP 2020","volume":"168","author":"Cai Jin-Yi","year":"2020","unstructured":"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."},{"key":"e_1_2_1_14_1","volume-title":"Counting below #P: Classes, problems and descriptive complexity. Master's thesis","author":"Chalki Angeliki","year":"2016","unstructured":"Angeliki Chalki. Counting below #P: Classes, problems and descriptive complexity. Master's thesis, National and Kapodistrian University of Athens, Greece, 2016."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395119"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104627"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.055"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1195971.1195974"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1073-y"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.08.003"},{"key":"e_1_2_1_22_1","first-page":"43","article-title":"Generalized first-order spectra and polynomial-time recognizable sets","volume":"7","author":"Fagin Ronald","year":"1974","unstructured":"Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. SIAM-AMS Proceedings, 7:43--73, 1974.","journal-title":"SIAM-AMS Proceedings"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.034"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80024-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60246-1_134"},{"key":"e_1_2_1_26_1","first-page":"1","volume-title":"Proc. of ICALP 2021","volume":"198","author":"Friedrich Tobias","year":"2021","unstructured":"Tobias Friedrich, Andreas G\u00f6bel, 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."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20479"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371660"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088330X"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10710-017-9314-z"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2621"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3418056"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447013"},{"key":"e_1_2_1_35_1","series-title":"An EATCS Series","volume-title":"Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion. Texts in Theoretical Computer Science","author":"Lane","year":"2002","unstructured":"Lane A. Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2002."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/203610.203611"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"e_1_2_1_41_1","first-page":"551","volume-title":"Proc. of SODA 1995","author":"Kannan Sampath","year":"1995","unstructured":"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."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144501387141"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90038-2"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1703953"},{"key":"e_1_2_1_45_1","volume-title":"Proc. of PCI 2001","volume":"2563","author":"Kiayias Aggelos","year":"2001","unstructured":"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."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1002\/andp.18471481202"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1975-0373371-6"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/69304.69309"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90039-6"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.101"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.10.009"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90006-I"},{"key":"e_1_2_1_54_1","volume-title":"Proc. of PLS 2001, Panhellenic Logic Symposium","author":"Pagourtzis Aris","year":"2001","unstructured":"Aris Pagourtzis. On the complexity of hard counting problems with easy decision version. In Proc. of PLS 2001, Panhellenic Logic Symposium, 2001."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/11821069_64"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1101003"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1039"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781315367996"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"e_1_2_1_63_1","volume-title":"Computer vision: algorithms and applications","author":"Szeliski Richard","year":"2010","unstructured":"Richard Szeliski. Computer vision: algorithms and applications. Springer Science & Business Media, 2010."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1080\/14786436108243366"},{"key":"e_1_2_1_65_1","first-page":"514","volume-title":"Proc. of FOCS 1989","author":"Toda Seinosuke","year":"1989","unstructured":"Seinosuke Toda. On the computational power of PP and &oplus;. In Proc. of FOCS 1989, pages 514--519. IEEE Computer Society, 1989."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57785-8_162"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132538"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054191000066"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266407"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561064.3561072","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3561064.3561072","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:15Z","timestamp":1750182555000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561064.3561072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,30]]},"references-count":67,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["10.1145\/3561064.3561072"],"URL":"https:\/\/doi.org\/10.1145\/3561064.3561072","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2022,8,30]]},"assertion":[{"value":"2022-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}