Próbkowanie jednolicie losowego, satysfakcjonującego zadania

14
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). ϕ:{0,1}n{0,1}x{0,1}nϕ(x)=1x

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ϕ

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.

Thomas wspiera Monikę
źródło

Odpowiedzi:

19

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.

Lorenzo Najt
źródło