Jakie są obecnie najbardziej znane górne i dolne granice progu (nie) satysfakcji dla losowego k-sat i / lub 3-sat?

Chciałbym poznać aktualny stan przejścia fazowego dla losowego k-sat, biorąc pod uwagę n zmiennych i klauzul m, co jest najlepiej znanym c = m / n dla górnych i dolnych granic.

cc.complexity-theory sat lower-bounds upper-bounds phase-transition Tayfun Pay
źródło

Czy próbowałeś wyszukać referencje? por. meta.cstheory.stackexchange.com/questions/300/…

RJK

PS Wydaje mi się, że drugie trafienie w Google to swobodnie dostępny artykuł z odpowiedziami na twoje pytanie. (Artykuł arXiv z 2009 r. Autorstwa Coja-Oghlana).

RJK

Zobacz cstheory.stackexchange.com/questions/1130/... dla rozsądnie aktualnej perspektywy. Dalsze działania osób pracujących w tej dziedzinie, takich jak Amin Coja-Oghlan i Dimitris Achlioptas, to odpowiedź, której szukasz.

András Salamon,

Nadal nie otrzymałem jednoznacznej odpowiedzi. Będę wdzięczny, jeśli ktoś da mi jednoznaczną odpowiedź. Dzięki

Tayfun Zapłać

To pytanie może ci się przydać: cstheory.stackexchange.com/questions/2168/… . W szczególności zobacz pierwszą odpowiedź.

Giorgio Camerani,

Odpowiedzi:

Dimitris Achlioptas opisuje to w swoim artykule ankietowym z Handbook of Satisfiable ( PDF ).

$r_k$ $k \ge 3$ $m/n > r_k$ $k$ $m$ $n$ $m/n < r_k$ $m$ $n$ $k$ $n$ dąży do nieskończoności, prawdopodobieństwo spełnienia wynosi odpowiednio 0 lub 1 w tych dwóch reżimach.)

$r_k$

k 3 4 5 7 10 20
Najlepsza górna granica 4,51 10,23 21,33 87,88 708,94 726,817
Najlepsza dolna granica 3,52 7,91 18,79 84,82 704,94 726,809

(ta tabela pojawia się na stronie oznaczonej jako 247 w wersji roboczej).

$k$ $r_k = 2^k\ln 2 - (1+\ln 2)/2 + o(1)$ $o(1)$ $k$

András Salamon
źródło