Tautologías / contradicciones de casos promedio, más allá del modelo aleatorio k-CNF

Es bien sabido que las fórmulas aleatorias -CNF sobre n variables con c n cláusulas son insatisfactorias (es decir, son contradicciones) con alta probabilidad, para una constante c suficientemente grande . Por lo tanto, las fórmulas aleatorias de k -CNF (para c lo suficientemente grande) constituyen una distribución natural sobre fórmulas booleanas insatisfactorias (o dualmente, sobre tautologías, es decir, negaciones de contradicciones). Esta distribución ha sido estudiada ampliamente.$k$$n$$cn$$c$$k$$c$

Mi pregunta es la siguiente : ¿existen otras distribuciones establecidas sobre tautologías o contradicciones proposicionales que puedan considerarse como la captura del "caso promedio" de tautologías o fórmulas insatisfactorias? ¿Se han estudiado intensamente estas distribuciones?

$G(n,p)$

Paul Beame, Russell Impagliazzo y Ashish Sabharwal. La complejidad de resolución de conjuntos independientes y cubiertas de vértices en gráficos aleatorios. Complejidad computacional, 16 (3): 245-297, 2007.

Paul Beame, Joe Culberson, David Mitchell y Cristopher Moore. La complejidad de la resolución de la aleatoriedad de coloración gráfica k Matemática Aplicada Discreta, 153: 25-47, 2005.