Pobieranie próbek zadowalających wzorów 3-SAT

Rozważ następujące zadanie obliczeniowe: Chcemy pobrać próbkę 3-SAT formuły zmiennych (wariant: zmiennych klauzule m ) w odniesieniu do równomiernego rozkładu prawdopodobieństwa, pod warunkiem spełnienia wzoru:$n$$n$$m$

P1: Czy można to skutecznie osiągnąć za pomocą klasycznego komputera (z losowymi bitami)?

P2: Czy można to skutecznie osiągnąć za pomocą komputera kwantowego?

Interesują mnie również następujące dwa warianty:

V2: Próbkujesz wszystkie formuły względem rozkładu prawdopodobieństwa, który daje satysfakcjonujące formuły dwukrotnie większe niż niezadowalające formuły.

V3: próbkujesz, gdzie waga jest liczbą satysfakcjonujących zadań (tutaj dbamy tylko o Q2).

Aktualizacja: odpowiedź Colinsa pokazuje prosty algorytm dla V3. (Myliłem się, zakładając, że jest to klasycznie trudne). Pozwól mi wspomnieć o innym wariancie wszystkich trzech pytań:

Z góry określasz klauzule $m$ i musisz próbkować losowo zadowalające podzbiory klauzul wejściowych.

Istnieje prosty algorytm dla V3. Będę używał konwencji, że istnieją możliwe klauzule, więc 2 ^ {8n ^ 3} formuły. (To tylko dla uproszczenia - jeśli nie chcesz, aby wszystkie klauzule 8n ^ 3 były uważane za prawidłowe, nie wpłynie to na następujący argument).$(2n)^3$$2^{8n^3}$$8n^3$

Wybierz losowe przypisanie z . Dla każdej z możliwych klauzul, które są prawdziwe w tym przypisaniu, klauzulę z prawdopodobieństwem . Każda formuła pojawi się z prawdopodobieństwem proporcjonalnym do liczby spełniających ją zadań. -clause wariant podobny pick zestaw rozmiarów się z punktach.$\{0,1\}^n$$7n^3$$1/2$$\phi$$m$$m$$7n^3$