<blockquote>
<b>Problem:</b> 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).
</blockquote>

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

<blockquote>
<b>Question:</b> 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?
</blockquote>

<p>Alternatively, is there a polynomial-time algorithm assuming NP=P?</p>

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

<hr>

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

<p>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.</p>

<np-hardness><counting-complexity><reductions>
Sampling a uniformly random satisfying assignment
Thomas Steinke
# Sampling a uniformly random satisfying assignment

(Asked by: username_0 on 2015-09-27)

> **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.

**Tags:** np-hardness, counting-complexity, reductions

---

## 0 answers

