Page 143 - 《软件学报》2025年第10期

4540 软件学报 2025 年第 36 卷第 10 期

[4] Vadhan SP. The complexity of counting in sparse, regular, and planar graphs. SIAM Journal on Computing, 2001, 31(2): 398–427. [doi:
10.1137/S0097539797321602]
[5] Goodfellow I, Bengio Y, Courville A. Deep Learning. Cambridge: MIT Press, 2016. 587–614.
[6] Valiant LG. The complexity of computing the permanent. Theoretical Computer Science, 1979, 8(2): 189–201. [doi: 10.1016/0304-3975
(79)90044-6]
[7] Patel V, Regts G. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM Journal
on Computing, 2017, 46(6): 1893–1919. [doi: 10.1137/16M1101003]
[8] Kolmogorov V. A faster approximation algorithm for the Gibbs partition function. In: Proc. of the 31st Conf. on Learning Theory.
Stockholm: PMLR, 2018. 228–249.
[9] Qiu GL, Zhang CH. Approximability of partition functions of ferromagnetic two-state spin systems. Computer Science, 2020, 47(5):
22–26 (in Chinese with English abstract). [doi: 10.11896/jsjkx.200200119]
[10] Bai ZL, Wang HP, Cao YZ, Wang LL. Fast sampling algorithms for spin systems on trees. Chinese Journal of Computers, 2022, 45(10):
2093–2116 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2022.02093]
[11] Laba HP, Tkachuk VM. Calculation of partition function of Ising model on quantum computer. Physics Letters A, 2023, 491: 129213.
[doi: 10.1016/j.physleta.2023.129213]
[12] Cornelissen A, Hamoudi Y. A sublinear-time quantum algorithm for approximating partition functions. In: Proc. of the 2023 Annual
ACM-SIAM Symp. on Discrete Algorithms (SODA). Florence: SIAM, 2023. 1245–1264. [doi: 10.1137/1.9781611977554.ch46]
[13] Barvinok A. Combinatorics and Complexity of Partition Functions. Cham: Springer, 2016. 1–7. [doi: 10.1007/978-3-319-51829-9]
[14] Dyer M, Greenhill C. The complexity of counting graph homomorphisms. Random Structures & Algorithms, 2000, 17(3–4): 260–289.
[doi: 10.1002/1098-2418(200010/12)17:3/4<260::AID-RSA5>3.0.CO;2-W]
[15] Goldberg LA, Grohe M, Jerrum M, Thurley M. A complexity dichotomy for partition functions with mixed signs. SIAM Journal on
Computing, 2010, 39(7): 3336–3402. [doi: 10.1137/090757496]
[16] Bulatov A, Grohe M. The complexity of partition functions. Theoretical Computer Science, 2005, 348(2-3): 148–186. [doi: 10.1016/j.tcs.
2005.09.011]
[17] Cai JY, Kowalczyk M. Spin systems on k-regular graphs with complex edge functions. Theoretical Computer Science, 2012, 461: 2–16.
[doi: 10.1016/j.tcs.2012.01.021]
[18] Cai JY, Fu ZG, Girstmair K, Kowalczyk M. A complexity trichotomy for k-regular asymmetric spin systems using number theory. In:
Proc. of the 9th Innovations in Theoretical Computer Science Conf. (ITCS 2018). Cambridge: ITCS, 2018. 2:1–2:22. [doi: 10.4230/
LIPIcs.ITCS.2018.2]
[19] Cai JY, Kowalczyk M. Partition functions on k-regular graphs with {0, 1}-vertex assignments and real edge functions. Theoretical
Computer Science, 2013, 494: 63–74. [doi: 10.1016/j.tcs.2012.12.043]
[20] Kowalczyk M, Cai JY. Holant problems for 3-regular graphs with complex edge functions. Theory of Computing Systems, 2016, 59(1):
133–158. [doi: 10.1007/s00224-016-9671-7]
[21] Impagliazzo R, Paturi R, Zane F. Which problems have strongly exponential complexity? Journal of Computer and System Sciences,
2001, 63(4): 512–530. [doi: 10.1006/jcss.2001.1774]
[22] Impagliazzo R, Paturi R. On the complexity of k-SAT. Journal of Computer and System Sciences, 2001, 62(2): 367–375. [doi: 10.1006/
jcss.2000.1727]
[23] Cygan M, Fomin FV, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S. Lower bounds based on the exponential-
time hypothesis. In: Cygan M, Fomin FV, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S, eds. Parameterized
Algorithms. Cham: Springer, 2015. 467–521. [doi: 10.1007/978-3-319-21275-3_14]
[24] Dell H, Husfeldt T, Marx D, Taslaman N, Wahlén M. Exponential time complexity of the permanent and the Tutte polynomial. ACM
Trans. on Algorithms (TALG), 2014, 10(4): 21. [doi: 10.1145/2635812]
[25] Curticapean R. Block interpolation: A framework for tight exponential-time counting complexity. Information and Computation, 2018,
261: 265–280. [doi: 10.1016/j.ic.2018.02.008]
[26] Liu Y. Exponential time complexity of the complex weighted Boolean #CSP. In: Wu WL, Tong G, eds. Computing and Combinatorics:
29th Int’l Conf. Cham: Springer, 2024. 83–96. [doi: 10.1007/978-3-031-49190-0_6]
[27] Björklund A, Kaski P. The fine-grained complexity of computing the Tutte polynomial of a linear matroid. In: Proc. of the 32nd Annual
ACM-SIAM Symp. on Discrete Algorithms. Philadelphia: SIAM, 2021. 2333–2345.
[28] Brand C, Dell H, Roth M. Fine-grained dichotomies for the Tutte plane and Boolean #CSP. Algorithmica, 2019, 81(2): 541–556. [doi: 10.
1007/s00453-018-0472-z]