Sampling Counting Input:a CSP formula =(V,C) Output .(sampling)uniform random satisfying solution .(counting)#of satisfying solutions .u:uniform distribution over all satisfying solutions of Rejection Sampling generate a uniform random Vx∈Q1×Q2×…×2mi if (x)=True then accept else reject; u is the distribution of accept) SAT solutions may be exponentially rare!• μ: uniform distribution over all satisfying solutions of Φ Sampling & Counting generate a uniform random ; if then accept else reject; is the distribution of ∀x ∈ Q1 × Q2 × ⋯ × Qm Φ(x) = 𝚃𝚛𝚞𝚎 μ (x ∣ accept) Rejection Sampling SAT solutions may be exponentially rare! Input: a CSP formula Output : • (sampling) uniform random satisfying solution • (counting) # of satisfying solutions Φ = (V, Q,C)