Próbkowanie jednolicie losowego, satysfakcjonującego zadania

Problem: Biorąc pod uwagę reprezentowane przez obwód logiczny, wygeneruj równomiernie losowy x ∈ { 0 , 1 } n taki, że ϕ ( x ) = 1 (lub wyjście ⊥, jeśli nie ma takiego x istnieje). $\phi : \{0,1\}^n \to \{0,1\}$$x \in \{0,1\}^n$$\phi(x)=1$$\perp$$x$

Najwyraźniej ten problem jest trudny NP. Moje pytanie brzmi, czy ten problem jest również „NP-łatwy”:

Pytanie: Czy istnieje algorytm, który rozwiązuje powyższy problem w czasie wielomianu w a wielkość obwodu cp otrzymać dostęp do wyroczni SAT? $n$$\phi$

Alternatywnie, czy istnieje algorytm wielomianowy przyjmujący, że NP = P?

Oczywiście wystarczający jest dostęp do wyroczni #SAT, więc złożoność leży gdzieś między NP a #P.

Wydaje mi się, że należy to wcześniej zbadać, ale nie mogę znaleźć odpowiedzi w Google.

Wiem, jak rozwiązać problem w przybliżeniu (tj. Wygenerować satysfakcjonujące zadanie, które jest statystycznie zbliżone do munduru) przy użyciu wariantu twierdzenia Valiant-Vazirani i / lub przybliżonego zliczania, ale uzyskanie dokładnie jednolitego wydaje się być innym problemem.

Tak.

(wykonaj kopię zapasową linków na wypadek awarii jednego: 1 2 3 4 )

Utwórz kopię zapasową na wypadek, gdyby wszystkie linki się zepsuły: Bellare, Mihir, Oded Goldreich i Erez Petrank. „Jednolita generacja świadków NP przy użyciu wyroczni NP”. Informacje i obliczenia 163,2 (2000): 510–526.