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).
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?
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.
źródło