{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T16:49:32Z","timestamp":1774630172006,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":30,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819723393","type":"print"},{"value":"9789819723409","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-981-97-2340-9_18","type":"book-chapter","created":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T23:01:51Z","timestamp":1714690911000},"page":"209-220","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the\u00a0Power of\u00a0Counting the\u00a0Total Number of\u00a0Computation Paths of\u00a0NPTMs"],"prefix":"10.1007","author":[{"given":"Eleni","family":"Bakali","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5378-0467","authenticated-orcid":false,"given":"Aggeliki","family":"Chalki","sequence":"additional","affiliation":[]},{"given":"Sotiris","family":"Kanellopoulos","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6220-3722","authenticated-orcid":false,"given":"Aris","family":"Pagourtzis","sequence":"additional","affiliation":[]},{"given":"Stathis","family":"Zachos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","unstructured":"Achilleos, A., Chalki, A.: Counting computations with formulae: logical characterisations of counting complexity classes. In: Proceedings of MFCS 2023. LIPICs, vol. 272, pp. 7:1\u20137:15 (2023). https:\/\/doi.org\/10.4230\/LIPICS.MFCS.2023.7","DOI":"10.4230\/LIPICS.MFCS.2023.7"},{"issue":"6","key":"18_CR2","doi-asserted-by":"publisher","first-page":"1193","DOI":"10.1137\/0217075","volume":"17","author":"E Allender","year":"1988","unstructured":"Allender, E., Rubinstein, R.S.: P-printable sets. SIAM J. Comput. 17(6), 1193\u20131202 (1988). https:\/\/doi.org\/10.1137\/0217075","journal-title":"SIAM J. Comput."},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/J.TCS.2022.02.030","volume":"915","author":"A Antonopoulos","year":"2022","unstructured":"Antonopoulos, A., Bakali, E., Chalki, A., Pagourtzis, A., Pantavos, P., Zachos, S.: Completeness, approximability and exponential time results for counting problems with easy decision version. Theoret. Comput. Sci. 915, 55\u201373 (2022). https:\/\/doi.org\/10.1016\/J.TCS.2022.02.030","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR4","doi-asserted-by":"publisher","unstructured":"Arenas, M., Mu\u00f1oz, M., Riveros, C.: Descriptive complexity for counting complexity classes. Logical Methods Comput. Sci. 16(1) (2020). https:\/\/doi.org\/10.23638\/LMCS-16(1:9)2020","DOI":"10.23638\/LMCS-16(1:9)2020"},{"issue":"5","key":"18_CR5","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1016\/j.ic.2006.02.002","volume":"204","author":"V Arvind","year":"2006","unstructured":"Arvind, V., Kurur, P.P.: Graph isomorphism is in SPP. Inf. Comput. 204(5), 835\u2013852 (2006). https:\/\/doi.org\/10.1016\/j.ic.2006.02.002","journal-title":"Inf. Comput."},{"key":"18_CR6","doi-asserted-by":"publisher","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In: Proceedings of STOC 2016, pp. 684\u2013697 (2016). https:\/\/doi.org\/10.1145\/2897518.2897542","DOI":"10.1145\/2897518.2897542"},{"key":"18_CR7","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-030-59267-7_22","volume-title":"Theory and Applications of Models of Computation","author":"E Bakali","year":"2020","unstructured":"Bakali, E., Chalki, A., Pagourtzis, A.: Characterizations and approximability of hard counting classes below #P. In: Chen, J., Feng, Q., Xu, J. (eds.) TAMC 2020. LNCS, vol. 12337, pp. 251\u2013262. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-59267-7_22"},{"issue":"1","key":"18_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(92)90084-S","volume":"103","author":"R Beigel","year":"1992","unstructured":"Beigel, R., Gill, J.: Counting classes: thresholds, parity, mods, and fewness. Theoret. Comput. Sci. 103(1), 3\u201323 (1992). https:\/\/doi.org\/10.1016\/0304-3975(92)90084-S","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR9","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BFb0028987","volume-title":"STACS 89","author":"JY Cai","year":"1989","unstructured":"Cai, J.Y., Hemachandra, L.A.: On the power of parity polynomial time. In: Monien, B., Cori, R. (eds.) STACS 89. LNCS, vol. 349, pp. 229\u2013239. Springer, Heidelberg (1989). https:\/\/doi.org\/10.1007\/BFb0028987"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1137\/0221022","volume":"21","author":"PC Chen","year":"1992","unstructured":"Chen, P.C.: Heuristic sampling: a method for predicting the performance of tree searching programs. SIAM J. Comput. 21, 295\u2013315 (1992). https:\/\/doi.org\/10.1137\/0221022","journal-title":"SIAM J. Comput."},{"key":"18_CR11","doi-asserted-by":"publisher","unstructured":"Curticapean, R.: The simple, little and slow things count : on parameterized counting complexity. PhD thesis (2015). https:\/\/doi.org\/10.22028\/D291-26612","DOI":"10.22028\/D291-26612"},{"issue":"1","key":"18_CR12","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0022-0000(05)80024-8","volume":"48","author":"SA Fenner","year":"1994","unstructured":"Fenner, S.A., Fortnow, L., Kurtz, S.A.: Gap-definable counting classes. J. Comput. Syst. Sci. 48(1), 116\u2013148 (1994). https:\/\/doi.org\/10.1016\/S0022-0000(05)80024-8","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"18_CR13","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J Gill","year":"1977","unstructured":"Gill, J.: Computational complexity of probabilistic turing machines. SIAM J. Comput. 6(4), 675\u2013695 (1977). https:\/\/doi.org\/10.1137\/0206049","journal-title":"SIAM J. Comput."},{"issue":"3","key":"18_CR14","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(90)90081-R","volume":"74","author":"U Hertrampf","year":"1990","unstructured":"Hertrampf, U.: Relations among mod-classes. Theoret. Comput. Sci. 74(3), 325\u2013328 (1990). https:\/\/doi.org\/10.1016\/0304-3975(90)90081-R","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/3-540-38076-0_29","volume-title":"Advances in Informatics","author":"A Kiayias","year":"2001","unstructured":"Kiayias, A., Pagourtzis, A., Sharma, K., Zachos, S.: Acceptor-definable counting classes. In: Manolopoulos, Y., Evripidou, S., Kakas, A.C. (eds.) PCI 2001. LNCS, vol. 2563, pp. 453\u2013463. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-38076-0_29"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"122","DOI":"10.2307\/2005469","volume":"29","author":"D Knuth","year":"1974","unstructured":"Knuth, D.: Estimating the efficiency of backtrack programs. Math. Comput. 29, 122\u2013136 (1974). https:\/\/doi.org\/10.2307\/2005469","journal-title":"Math. Comput."},{"key":"18_CR17","doi-asserted-by":"publisher","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The Graph Isomorphism Problem: Its Structural Complexity. Progress in Theoretical Computer Science. Birkh\u00e4user\/Springer (1993). https:\/\/doi.org\/10.1007\/978-1-4612-0333-9","DOI":"10.1007\/978-1-4612-0333-9"},{"issue":"3","key":"18_CR18","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0022-0000(93)90006-I","volume":"46","author":"M Ogiwara","year":"1993","unstructured":"Ogiwara, M., Hemachandra, L.A.: A complexity theory for feasible closure properties. J. Comput. Syst. Sci. 46(3), 295\u2013325 (1993). https:\/\/doi.org\/10.1016\/0022-0000(93)90006-I","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR19","doi-asserted-by":"publisher","unstructured":"Pagourtzis, A., Zachos, S.: The complexity of counting functions with easy decision version. In: Proceedings of MFCS, vol. 2006, pp. 741\u2013752 (2006). https:\/\/doi.org\/10.1007\/11821069_64","DOI":"10.1007\/11821069_64"},{"key":"18_CR20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BFb0009651","volume-title":"Theoretical Computer Science","author":"CH Papadimitriou","year":"1983","unstructured":"Papadimitriou, C.H., Zachos, S.K.: Two remarks on the power of counting. In: Cremers, A.B., Kriegel, H.P. (eds.) Theoretical Computer Science. LNCS, vol. 145, pp. 269\u2013276. Springer, Heidelberg (1983). https:\/\/doi.org\/10.1007\/BFb0009651"},{"key":"18_CR21","unstructured":"Pay, T., Cox, J.L.: An overview of some semantic and syntactic complexity classes. In: Electronic Colloquium on Computational Complexity, TR18-166 (2018). https:\/\/eccc.weizmann.ac.il\/report\/2018\/166"},{"issue":"4","key":"18_CR22","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1137\/0207038","volume":"7","author":"PW Purdom","year":"1978","unstructured":"Purdom, P.W.: Tree size by partial backtracking. SIAM J. Comput. 7(4), 481\u2013491 (1978). https:\/\/doi.org\/10.1137\/0207038","journal-title":"SIAM J. Comput."},{"issue":"4","key":"18_CR23","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0020-0190(94)90123-6","volume":"52","author":"RP Rao","year":"1994","unstructured":"Rao, R.P., Rothe, J., Watanabe, O.: Upward separation for FewP and related classes. Inf. Process. Lett. 52(4), 175\u2013180 (1994). https:\/\/doi.org\/10.1016\/0020-0190(94)90123-6","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"18_CR24","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U Sch\u00f6ning","year":"1988","unstructured":"Sch\u00f6ning, U.: Graph isomorphism is in the low hierarchy. J. Comput. Syst. Sci. 37(3), 312\u2013323 (1988). https:\/\/doi.org\/10.1016\/0022-0000(88)90010-4","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR25","unstructured":"Simon, J.: On some central problems in computational complexity. PhD thesis (1975)"},{"issue":"5","key":"18_CR26","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput. 20(5), 865\u2013877 (1991). https:\/\/doi.org\/10.1137\/0220053","journal-title":"SIAM J. Comput."},{"issue":"1","key":"18_CR27","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"LG Valiant","year":"1976","unstructured":"Valiant, L.G.: Relative complexity of checking and evaluating. Inf. Process. Lett. 5(1), 20\u201323 (1976). https:\/\/doi.org\/10.1016\/0020-0190(76)90097-1","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"18_CR28","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci. 8(2), 189\u2013201 (1979). https:\/\/doi.org\/10.1016\/0304-3975(79)90044-6","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR29","doi-asserted-by":"publisher","unstructured":"Valiant, L.G.: Accidental algorithms. In: Proceedings of FOCS, vol. 2006, pp. 509\u2013517 (2006). https:\/\/doi.org\/10.1109\/FOCS.2006.7","DOI":"10.1109\/FOCS.2006.7"},{"key":"18_CR30","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"LG Valiant","year":"1986","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theoret. Comput. Sci. 47, 85\u201393 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90135-0","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-97-2340-9_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T23:03:18Z","timestamp":1714690998000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-97-2340-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819723393","9789819723409"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-981-97-2340-9_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"3 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TAMC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual Conference on Theory and Applications of Models of Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hong Kong","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 May 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 May 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tamc2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tamc2024.comp.polyu.edu.hk\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}