Warunki podatności na zadowalanie 3SAT-Satisfiable

Zastanawiam się konkretnie, czy istnieje interesujący warunek dotyczący odsetka zadań spełniających formułę 3SAT, aby zagwarantować, że takie problemy są możliwe do rozwiązania.

Załóżmy na przykład, że klasa problemów 3SAT z możliwych przypisań spełnia wzór logiczny; czy możemy skutecznie znaleźć satysfakcjonujące zadanie? Po co wynika problem w P? $\epsilon(n) 2^n$ $2^n$ $\epsilon$

Edycja uwaga: Zastępuje z , aby wyjaśnić nieporozumienia. $\epsilon$ $\epsilon(n)$

cc.complexity-theory ds.algorithms sat np Rafi Witten
źródło

Prosta obserwacja: jeśli

jest co najwyżej odwrotnie wielomianowo małe, wówczas równomierne próbkowanie

razy da rozwiązanie w oczekiwanym czasie wielomianu. Więc jeśli

jest między 1 a 1 / poli (n), problem jest prosty (dotyczy ZPP).

ϵ

$\epsilon$

1 / ϵ

$1/\epsilon$

ϵ

$\epsilon$

Robin Kothari,

podobnie, jeśli 1 / eps jest quasipolynomial, to masz losowy algorytm quasipoly czasu, co samo w sobie byłoby zaskakujące

Suresh Venkat

Odpowiedzi:

$0< \epsilon <1$ $1/\textit{polylog}(n)$ $\epsilon 2^n$

Algorytmy nie są trudne:

$S$ $S$

$\epsilon$

$S$ $S$ $S$

Algorytmem dla 2SAT jest myśl, że już w słynnym artykule S. Cooka z 1971 roku.

Algorytm dla 3CNF pochodzi z: L. Trevisan Uwaga na temat deterministycznego zliczania przybliżonego dla k-DNF w Proc. APPROX-RANDOM, Springer-Verlag, strony 417-426, 2004

Oryginalny artykuł pokazujący wynik dla 3CNF to: E. Hirsch, szybki deterministyczny algorytm dla formuł, które mają wiele satysfakcjonujących przypisań , Journal of IGPL, 6 (1): 59-71, 1998

Iddo Tzameret
źródło

ϵ

$\epsilon$

ϵ = 1 / p o l y l o g (n)

$\epsilon = 1/polylog(n)$

Jak zbudować S?

Radu GRIGore

C_{1}

$C_1$

C_{2}

$C_2$

C_{1}

$C_1$