Teoretyczne informatyka random-k-sat

2

Bieżące najostrzejsze granice krytycznej gęstości 3-SAT

Interesuje mnie krytyczna gęstość 3-satysfakcji (3-SAT) . Przypuszcza się, że takie α istnieje: jeśli liczba losowo wygenerowanych klauzul 3-SAT wynosi ( α + ϵ ) n lub więcej, są prawie na pewno niezadowalające. (Tutaj ϵ jest dowolną małą stałą, a n jest liczbą zmiennych.) Jeśli liczba wynosi ( α - …

26 pr.probability random-k-sat

3

Czy były jakieś badania nad SAT powyżej progu satysfakcji?

Dobrze znaną cechą instancji SAT jest stosunek liczby klauzul do liczby zmiennych , tj. Iloraz . Dla każdego istnieje wartość progowa st \ dla , większość instancji jest zadowalająca, a dla większość instancji jest niezadowalająca. Przeprowadzono wiele badań dotyczących problemów, w których , oraz problemów z wystarczająco małym ,m n …

25 cc.complexity-theory sat random-k-sat phase-transition

1

Jaka jest złożoność liczenia losowego 2-SAT?

Czy podjęto prace nad tym, jak złożoność przypadkowych instancji # 2-SAT zmienia się w zależności od gęstości klauzuli? To znaczy: w jaki sposób trudność liczenia satysfakcjonujących rozwiązań dla losowo generowanej instancji 2-SAT różni się w zależności od gęstości klauzuli? W szczególności, czy znane są rygorystyczne wyniki dotyczące progów krytycznych? Oczywiście, …

18 cc.complexity-theory counting-complexity random-k-sat

1

Tautologie / sprzeczności średnich przypadków, poza przypadkowym modelem k-CNF

Jest dobrze wiadomo, że losowy Preparaty -cnf na n zmiennymi c n klauzule unsatisfiable (tj sprzeczności), z dużym prawdopodobieństwem, na wystarczająco dużej stałej C . Tak więc losowe formuły k- CNN (dla c wystarczająco dużych) stanowią naturalny rozkład w niezadowalających formułach boolowskich (lub podwójnie w tautologiach, tj. Negacjach sprzeczności). Ten …

16 cc.complexity-theory reference-request lo.logic sat random-k-sat

1

Random 3-SAT: Jaki jest eksperymentalny zakres progowy?

Krytyczny stosunek klauzul do zmiennych dla losowej 3-SAT jest większy niż 3 i mniejszy niż 6, i wydaje się być powszechnie opisywany jako „około 4,2” lub „około 4,25”. Mezard, Parisi i Zecchina udowadniają (w sensie fizyki), że współczynnik krytyczny wynosi 4,256, podczas gdy autorzy pierwszego i trzeciego dowodzą , że …

14 sat phase-transition random-k-sat

2

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

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ć …

11 graph-algorithms sat treewidth random-k-sat hard-instances

Pytania otagowane jako random-k-sat