Este artigo recente do FOCS2013, Strong Backdoors to Bounded Treewidth SAT de Gaspers e Szeider, fala sobre o vínculo entre a largura da árvore do gráfico da cláusula SAT e a dureza da instância.
Para instâncias aleatórias de 3-SAT, ou seja, 3-SAT escolhidas aleatoriamente, qual é a correlação entre a largura da árvore do gráfico de cláusulas e a dureza da instância?
A "dureza da instância" pode ser considerada "difícil para um solucionador SAT típico", ou seja, o tempo de execução.
Estou procurando respostas ou referências de estilo teórico ou empírico. Que eu saiba, não parece haver estudos empíricos sobre isso. Estou ciente de que existem maneiras um pouco diferentes de criar gráficos de cláusulas SAT, mas esta questão não está focada na distinção.
Talvez uma questão natural e intimamente relacionada seja como a largura da árvore do gráfico de cláusulas se relaciona com a transição de fase 3-SAT.