# Sampling a uniformly random satisfying assignment

Problem: Given $\phi : \{0,1\}^n \to \{0,1\}$ represented by a boolean circuit, generate a uniformly random $x \in \{0,1\}^n$ such that $\phi(x)=1$ (or output $\perp$ if no such $x$ exists).

Clearly this problem is NP-hard. My question is whether or not this problem is also "NP-easy":

Question: Does there exist an algorithm that solves the above problem in time polynomial in $n$ and the circuit size of $\phi$ given access to a SAT oracle?

Alternatively, is there a polynomial-time algorithm assuming NP=P?

Clearly having access to a #SAT oracle suffices, so the complexity lies somewhere between NP and #P.

I feel like this should have been studied before, but I can't find an answer on Google.

I know how to solve the problem approximately (i.e. generate a satisfying assignment that is statistically close to uniform) using a variant of the Valiant-Vazirani Theorem and/or approximate counting, but getting exactly uniform seems to be a different problem.

Yes.

(backup links in case that one goes down: 1 2 3 4)

Back up reference, in case all those links go down: Bellare, Mihir, Oded Goldreich, and Erez Petrank. "Uniform generation of NP-witnesses using an NP-oracle." Information and Computation 163.2 (2000): 510-526.