Mierzenie losowości wzorów CNF

Powszechnie wiadomo, że formuły CNF można z grubsza podzielić na 2 szerokie klasy: losowe i strukturalne. Strukturalne formuły CNF, w przeciwieństwie do losowych formuł CNF, wykazują pewien porządek, pokazując wzorce, które prawdopodobnie nie wystąpią przypadkowo. Można jednak znaleźć formuły strukturalne wykazujące pewien stopień losowości (tzn. Niektóre określone grupy klauzul wydają się znacznie mniej ustrukturyzowane niż inne), a także formuły losowe z pewną słabą formą struktury (tj. Niektóre określone grupy klauzul wydają się mniej losowe niż inne ). Stąd wydaje się, że losowość formuły nie jest tylko faktem tak / nie.

Niech będzie funkcją, która biorąc pod uwagę wzór CNF , zwraca rzeczywistą wartość z zakresu od do włącznie: oznacza formułę o czystej strukturze, podczas gdy oznacza czystą przypadkową formułę.F ∈ $r: \mathcal{F} \rightarrow [0,1]$$F \in \mathcal{F}$$0$$1$$0$$1$

Zastanawiam się, czy ktoś kiedykolwiek próbował wymyślić taki . Oczywiście wartość zwracana przez byłaby (przynajmniej taka jest moja intencja) tylko praktycznym pomiarem według pewnych rozsądnych kryteriów, a nie solidną teoretyczną prawdą.$r$$r$

Interesuje mnie również to, czy ktoś kiedykolwiek zdefiniował i przestudiował jakikolwiek wskaźnik statystyczny, który można zastosować w definicji lub w określeniu innych użytecznych ogólnych właściwości formuły. Przez wskaźnik statystyczny rozumiem coś takiego:$r$

1. HCV (uderzenie liczba wariancji)
   
   Niech jest funkcją, ponieważ zmienna , zwraca liczbę razy większej pojawia się w . Niech będzie zbiorem zmiennych wykorzystywanych w . Niech będzie AHC (średnia liczba ). HCV jest zdefiniowany następująco: $h_F: \mathbb{N} \rightarrow \mathbb{N}$$v_j \in \mathbb{N}$$v_j$$F$$V$$F$$\bar{h}_F = \frac{1}{|V|} \sum_{v_j \in V}{h_F(v_j)}$
   
   $HVC = \frac{1}{|V|} \sum_{v_j \in V}{(h_F(v_j) - \bar{h}_F)^2}$
   
   W przypadkowych przypadkach HCV jest bardzo niski (wszystkie zmienne są wymieniane prawie tyle samo razy), podczas gdy w strukturalnych przypadkach tak nie jest (niektóre zmienne są używane bardzo często, a inne nie, tj. Istnieją „klastry użytkowania” ).
   
   
2. AID (średni stopień zanieczyszczenia)
   
   Niech będzie liczbą przypadków, gdy wystąpi dodatnio, i niech liczbę razy, gdy wystąpi ujemna. Niech będzie funkcją, która przy zmiennej zwraca swój identyfikator (stopień zanieczyszczenia). Funkcja jest zdefiniowana następująco: . Zmienne występujące w połowie razy dodatnie, a w połowie razy ujemne mają maksymalny stopień zanieczyszczenia, podczas gdy zmienne występujące zawsze dodatnie lub zawsze ujemne (tj. Czyste literały) mają minimalny stopień zanieczyszczenia. AID jest po prostu zdefiniowany w następujący sposób: $h_F^{+}(v_j)$$v_j$$h_F^{-}(v_j)$$i: \mathbb{N} \rightarrow [0,1]$$v_j \in V$$i(v_j)$$i(v_j) = 2 \cdot \frac{min(h_F^{+}(v_j), h_F^{-}(v_j))}{h_F(v_j)}$
   
   $AID = \frac{1}{|V|} \sum_{v_j \in V}{i(v_j)}$
   
   W przypadkowych przypadkach (przynajmniej w tych generowanych przez negowanie zmiennych z prawdopodobieństwem ), AID jest prawie równy , podczas gdy w instancjach strukturalnych jest zwykle daleki od .$0.5$$1$$1$
   
   
3. IDV (wariancja stopnia zanieczyszczenia)
   
   IDV jest bardziej niezawodnym wskaźnikiem niż sam AID, ponieważ uwzględnia przypadkowe wystąpienia generowane przez negowanie zmiennych o prawdopodobieństwie innym niż . Jest zdefiniowany jako: W przypadkowych przypadkach IDV wynosi (ponieważ każda zmienna jest zanegowana z tym samym prawdopodobieństwem), podczas gdy w instancjach strukturalnych jest daleki od . $0.5$
   
   $IDV = \frac{1}{|V|} \sum_{v_j \in V}{(i(v_j) - AID)^2}$
   
   $0$$0$

Motywacje

1. Aby lepiej zrozumieć, jak działają formuły CNF, jak można zmierzyć ich losowość / strukturę, jeśli inne użyteczne ogólne właściwości można by wywnioskować, patrząc na ich wskaźniki statystyczne, czy i jak takie wskaźniki można by wykorzystać do przyspieszenia wyszukiwania.
2. Zastanawiam się, czy o satysfakcji (a nawet liczbie rozwiązań) wzoru CNF można wnioskować po prostu sprytnie manipulując jego wskaźnikami statystycznymi.

pytania

1. Czy ktoś kiedykolwiek zaproponował sposób pomiaru losowości formuły CNF?
2. Czy ktoś kiedykolwiek zaproponował jakiś wskaźnik statystyczny, który można by wykorzystać do badania, a nawet do mechanicznego wnioskowania przydatnych ogólnych właściwości formuły CNF?

Proponuję pożyczyć intuicję fizyki, że struktury „mniej losowe” są bardziej symetryczne. Symetria dla CNF to dowolna transformacja zmiennych, która utrzymuje niezmienność funkcji. Według tych kryteriów funkcje 3 zmiennych, takich jak

$\displaystyle x_{1} \vee x_{2} \vee x_{3} .$

lub powiedzmy

$\displaystyle(x_{1} \vee x_{2} \vee \neg x_{3}) \wedge (x_{1} \vee \neg x_{2} \vee x_{3}) \wedge (\neg x_{1} \vee x_{2} \vee x_{3}) \wedge (\neg x_{1} \vee \neg x_{2} \vee \neg x_{3}).$

są mniej przypadkowe niż, powiedzmy

$\displaystyle(x_{1} \vee x_{2} \vee \neg x_{3}) \wedge (x_{1} \vee \neg x_{2} \vee x_{3}) \wedge (\neg x_{1} \vee \neg x_{2} \vee x_{3}) .$

Ogólnie rzecz biorąc, zdefiniowanie pojęcia „losowego” na strukturach skończonych jest trudne. Historycznie wypróbowywano go na ciągach binarnych, które są prawdopodobnie najprostszymi strukturami skończonymi. Na przykład intuicyjnie sekwencja 01010101 jest „mniej losowa” niż, powiedzmy, 01001110. Szybko jednak zorientowano się, że nie ma spójnej formalnej definicji skończonej losowej sekwencji! Dlatego należy być sceptycznym wobec wszelkich naiwnych prób określenia miary losowości dla dowolnej skończonej struktury.