Medición de la aleatoriedad de las fórmulas CNF

Es ampliamente conocido que las fórmulas CNF se pueden dividir aproximadamente en 2 clases amplias: aleatoria versus estructurada. Las fórmulas estructuradas de CNF, en oposición a las fórmulas aleatorias de CNF, exhiben algún tipo de orden, mostrando patrones que es poco probable que ocurran por casualidad. Sin embargo, uno puede encontrar fórmulas estructuradas que muestran cierto grado de aleatoriedad (es decir, ciertos grupos específicos de cláusulas parecen mucho menos estructuradas que otras), así como fórmulas aleatorias con alguna forma débil de estructura (es decir, ciertos grupos específicos de cláusulas parecen menos aleatorias que otras ) Por lo tanto, parece que la aleatoriedad de una fórmula no es solo un hecho sí / no.

Sea una función que, dada una fórmula CNF F ∈ F , devuelve un valor real entre 0 y 1 inclusive: 0 significa una fórmula estructurada pura, mientras que 1 significa una fórmula aleatoria pura.$r: \mathcal{F} \rightarrow [0,1]$$F \in \mathcal{F}$$0$$1$$0$$1$

Me pregunto si alguien ha tratado de inventar tal . Por supuesto, el valor devuelto por r sería (al menos esta es mi intención) solo una medición práctica de acuerdo con algunos criterios razonables, en lugar de una verdad teórica sólida.$r$$r$

También me interesa saber si alguien ha definido y estudiado algún indicador estadístico que pueda usarse en la definición de , o en la determinación de otras propiedades generales útiles de una fórmula. Por indicador estadístico quiero decir algo así:$r$

1. HCV (Hit Count varianza)
   
   Deje sea una función que, dada una variable v j ∈ N , devuelve el número de veces v j aparece en F . Deje V el conjunto de variables utilizadas en F . Deje ˉ h F = $h_F: \mathbb{N} \rightarrow \mathbb{N}$$v_j \in \mathbb{N}$$v_j$$F$$V$$F$será el AHC (Recuento medio de aciertos). El VHC se define de la siguiente manera: HVC=$\bar{h}_F = \frac{1}{|V|} \sum_{v_j \in V}{h_F(v_j)}$
   
   En casos aleatorios, el VHC es muy bajo (todas las variables se mencionan casi el mismo número de veces), mientras que en casos estructurados no lo es (algunas variables se usan con mucha frecuencia y otros no, es decir, hay "grupos de uso").$HVC = \frac{1}{|V|} \sum_{v_j \in V}{(h_F(v_j) - \bar{h}_F)^2}$
   
   
   
   
2. 
   
   $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)}$
   
   $0.5$$1$$1$
   
   
3. 
   
   $0.5$
   
   $IDV = \frac{1}{|V|} \sum_{v_j \in V}{(i(v_j) - AID)^2}$
   
   $0$$0$

Motivaciones

1. Para comprender mejor cómo funcionan las fórmulas CNF, cómo se podría medir su aleatoriedad / estructura, si se pudieran inferir otras propiedades generales útiles al observar sus indicadores estadísticos, si estos indicadores se podrían usar para acelerar la búsqueda y de qué manera.
2. Me pregunto si la satisfacción (o incluso el número de soluciones) de una fórmula CNF podría inferirse simplemente manipulando inteligentemente sus indicadores estadísticos.

Preguntas

1. ¿Alguien alguna vez propuso una forma de medir la aleatoriedad de una fórmula CNF?
2. ¿Alguien propuso alguna vez algún indicador estadístico que pueda usarse para estudiar o incluso inferir mecánicamente propiedades generales útiles de una fórmula de CNF?

Sugiero tomar prestada la intuición de la física de que las estructuras "menos aleatorias" son más simétricas. La simetría para CNF es cualquier transformación de las variables, que mantiene invariable la función. Según ese criterio, las funciones de 3 variables como

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

o, digamos,

$\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}).$

son menos aleatorios que, digamos

$\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}) .$

En general, definir un concepto de "aleatorio" en estructuras finitas es un desafío. Históricamente, se probó en secuencias binarias, que posiblemente sean las estructuras finitas más simples. Por ejemplo, intuitivamente, una secuencia 01010101 es "menos aleatoria" que, por ejemplo, 01001110. ¡Sin embargo, se dio cuenta rápidamente de que no existe una definición formal consistente de secuencia aleatoria finita ! Por lo tanto, uno debe ser escéptico ante cualquier intento ingenuo de definir una medida de aleatoriedad para cualquier estructura finita.