Jaka jest korelacja między wysokością a twardością instancji dla losowego 3-SAT?

11

Ten ostatni artykuł z FOCS2013, Strong Backdoors to Bounded Treewidth SAT autorstwa Gaspersa i Szeidera mówi o związku między szerokością wykresu klauzuli SAT a twardością instancji.

W przypadku losowych instancji 3-SAT, tj. Instancji losowo wybranych 3-SAT, jaka jest korelacja między szerokością wykresu klauzulowego a twardością instancji?

„Twardość wystąpienia” może być traktowana jako „trudna dla typowego solwera SAT”, tj. Czas działania.

Szukam odpowiedzi lub odniesień w stylu teoretycznym lub empirycznym. Według mojej wiedzy wydaje się, że nie ma badań empirycznych na ten temat. Wiem, że istnieją nieco inne sposoby budowania grafów klauzul SAT, ale to pytanie nie koncentruje się na rozróżnieniu.

Być może naturalnym, ściśle powiązanym pytaniem jest to, jak szerokość wykresu klauzulowego odnosi się do przejścia fazowego 3-SAT.

— vzn
źródło

10

Naprawdę nie odpowiedź, ale najbliższe referencje, o których wiem. Dostępne są wyniki dla szerokości gałęzi. Ponadto istnieje co najmniej jedno badanie empiryczne dotyczące szerokości instancji przemysłowych.

Discovering treewidth , H. Bodlaender, 2005. Daje algorytmy do obliczania granic na treewidth.
Treewidth w przemysłowych testach porównawczych SAT , R. Mateescu, 2011. Wykorzystuje odmiany powyższych algorytmów do oszacowania powierzchni porównawczej testów porównawczych SAT2009.
Algorytmy i wyniki złożoności dla #SAT i wnioskowania bayesowskiego , F. Bacchus S. Dalmao, T. Pitassi, 2003. Odnosi szerokość gałęzi do złożoności #SAT, 2003.
Satysfakcja, tautologie szerokości gałęzi i tseityny , Alehnovich, Razborov, 2002.

— Vijay D.
źródło

7

Zasadniczo nie można oczekiwać, że przypadkowe przypadki SAT ograniczą szerokość, nawet jeśli są łatwe. Oto przykład:

$n$ $3$ $\theta(n)$ $3$

$d$ $k$ $4 \cdot \frac{1}{2^k} \cdot dk \leq 1$ $d \leq \frac{2^k}{4k}$

$t$ $t$ $n/2$

— Daniello
źródło

dzięki za pomysły. ofc nie spodziewał się, że przypadkowe przypadki ograniczyłyby szerokość; przeciwnie można przypuszczać bez większych trudności. ale jest to parametr liczbowy, który można porównać / skorelować z twardością podobnie jak wiele innych parametrów badanych w badaniach empirycznych punktów przejściowych SAT, i wydaje się, że na podstawie istniejących badań można oczekiwać pewnej zależności lub korelacji.

— vzn

@vzn Chodzi mi bardziej o to, że w najpopularniejszych modelach losowych szerokość dachu przechodzi przez dach, zanim instancje staną się trudne obliczeniowo. Z drugiej strony, instancje `` z prawdziwego życia '' prawdopodobnie mają znacznie mniejszą szerokość niż przypadkowe i spodziewam się, że solwery SAT wykorzystają (niektóre) to.

— daniello