Approximate Counting fix A= partition function: zA(G)=∑Π Aa(u),o(v) o∈{0,1}V(u,w)∈E is a well-define computational problem poly-time computable if By=1 or (B,Y)=(0,0) #P-hard if otherwise Approximation!Approximate Counting ZA(G) = ￾ ￾￾{0,1}V ￾ (u,v)￾E A￾(u),￾(v) partition function: A = ￾ A0,0 A0,1 A1,0 A1,1 ￾ = ￾ ￾ 1 1 ￾ ￾ fix is a well-define computational problem poly-time computable if ￾￾ = 1 or (￾, ￾) = (0, 0) #P-hard if otherwise Approximation!