Ile wystąpień 3-SAT jest zadowalających?

28

Rozważ problem 3-SAT na n zmiennych. Liczba możliwych odrębnych klauzul wynosi:

C = 2 n \times 2 (n - 1) \times 2 (n - 2) / 3! = 4 n (n - 1) (n - 2) / 3 .

$C = 2n \times 2(n-1) \times 2(n -2) / 3! = 4 n(n-1)(n-2)/3 \text.$

Liczba przypadków problemem jest ilość wszystkich podzbiorów zestawu możliwych punktach: . Trywialnie, dla każdego istnieje co najmniej jeden przypadek satysfakcjonujący i jeden przypadek niezadowalający. Czy można obliczyć lub przynajmniej oszacować liczbę zadowalających wystąpień dla dowolnego n? $I = 2^C$ $n \ge 3$

cc.complexity-theory sat Antonio Valerio Miceli-Barone
źródło

Zobacz także podobne pytanie cstheory.stackexchange.com/q/14953

András Salamon

Czy masz coś przeciwko wyjaśnieniu, w jaki sposób otrzymujesz wzór liczenia? Gdzie jest 3! pochodzić itp?

Yan King Yin

Kolejne pytanie dla początkujących: jeśli całkowita liczba konfiguracji (tj. Przypisania prawdy) wynosi

, oznacza to, że żadna instancja problemu nie może wyrazić wielu przypisań prawdy. Jest to sprzeczne z intuicją dla mojej wiedzy, że formuły boolowskie są kompletne w tym sensie, że mogą wyrażać dowolną tabelę prawdy. Co tu jest haczyk?

2^{2^{n}} ≫ 2^{C}

$2^{2^n} \gg 2^C$

Yan King Yin

27

Długa historia prac nad przejściami faz w SAT wykazała, że dla każdego ustalonego istnieje próg sparametryzowany stosunkiem liczby klauzul do który decyduje o spełnieniu. Z grubsza mówiąc, jeśli stosunek jest mniejszy niż 4,2, to z przeważającym prawdopodobieństwem instancja jest zadowalająca (a zatem ogromna część liczby instancji z tyloma klauzulami i zmiennymi jest zadowalająca). Jeśli współczynnik ten jest nieco powyżej 4,2, wówczas obowiązuje odwrotność - przytłaczająca część przypadków jest niezadowalająca. $n$ $n$

Odniesień jest o wiele za dużo, aby tu cytować: jednym źródłem informacji jest książka Mezarda i Montanari . Jeśli ktoś ma źródła do ankiet itp. Na ten temat, może opublikować je w komentarzach lub edytować tę odpowiedź (zrobię to CW)

Referencje:
- badanie Achlioptas
- Jeżeli naprawdę trudne problemy
- Udoskonalenie przejście fazowe w poszukiwaniu kombinatorycznej

Suresh Venkat
źródło

To jest bardzo interesujące. Jakie jest „przytłaczające prawdopodobieństwo?” Czy to coś w 75%, czy 99,9999%?

Philip White

Szczerze mówiąc, nie pamiętam. jest sparametryzowany przez odległość stosunku od punktu przełączenia i działa jak sigmoid (więc bardzo szybko dochodzi do 1). Powiązane ankiety mają prawdopodobnie więcej szczegółów

Suresh Venkat

1

k

$k$

17

$2^{|C|}$

$2^{(7/8)|C|}$

$2^n$ $|C|=O(n^3)$

Magnus Wahlström
źródło

3^{n} - 2^{n}

$3^n-2^n$

3^{n} - 2^{n} - 2^{n - 1}

$3^n-2^n-2^{n-1}$

<

$<$

n u m b e r o f c l a u s e s

$number of clauses$

\leq

$\leq$

3^{n} - 2^{n}

$3^n-2^n$ wówczas te przypadki były wyjątkowo satysfakcjonujące lub niezadowalające. Nie przypominam sobie wyprowadzenia dla 3-SAT na czubku głowy. Ok

Tayfun Zapłać

4

Ta odpowiedź dotyczy tylko tempa wzrostu liczby zadowalających przypadków.

$A$ $O(n^k)$ $k$ $NP$ $P=NP$

Mohammad Al-Turkistany
źródło

Ile wystąpień 3-SAT jest zadowalających?

Odpowiedzi: