US93] Jerrum-Sinclair'93 [GJP03]Goldberg-Jerrum-Paterson'03 Y 3 ferromagnetic 2-state spin 2.5 87=1 FPRAS [GJP03] ferromagnetic Ising Model 1.5 anti- .FPRAS [JS93] ferromagnetic 1.11017 1 0≤B,Y≤1 0.5 no FPRAS unless NPCRP FPRAS [GJP03] [GJP03] 、heat-bath 8 0.5 1 1.5 2 2.5 30 0.5 1 1.5 2 2.5 3 0 0.5 1 1.5 2 2.5 3
0< , <1 = 1 uniqueness threshold threshold achieved by heatbath random walk 1.11017 0 ￾ ￾, ￾ ￾ 1 ￾ ￾ ferromagnetic Ising Model ferromagnetic 2-state spin FPRAS [JS93] FPRAS [GJP03] FPRAS [GJP03] heat-bath no FPRAS unless NP⊆RP [GJP03] anti￾ferromagnetic Goldberg-Jerrum-Paterson’03 Jerrum-Sinclair’93 [GJP03] [JS93]