14
$\begingroup$
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.

$\endgroup$
19
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.