Medindo a aleatoriedade das fórmulas CNF

12

É sabido que as fórmulas CNF podem ser divididas em 2 classes amplas: aleatória versus estruturada. As fórmulas estruturadas de CNF, em oposição às fórmulas aleatórias de CNF, exibem algum tipo de ordem, mostrando padrões que dificilmente acontecerão por acaso. No entanto, pode-se encontrar fórmulas estruturadas mostrando algum grau de aleatoriedade (ou seja, certos grupos específicos de cláusulas parecem muito menos estruturadas que outras), bem como fórmulas aleatórias com alguma forma fraca de estrutura (ou seja, certos grupos específicos de cláusulas parecem menos aleatórias que outras ) Portanto, parece que a aleatoriedade de uma fórmula não é apenas um fato sim / não.

Seja uma função que, dada uma fórmula CNF F F , retorne um valor real entre 0 e 1 inclusive: 0 significa uma fórmula estruturada pura, enquanto 1 significa uma fórmula aleatória pura.r:F[0,1]FF0101

Gostaria de saber se alguém já tentou inventar um . É claro que o valor retornado por r seria (pelo menos essa é a minha intenção) apenas uma medida prática de acordo com alguns critérios razoáveis, e não uma verdade teórica sólida.rr

Também estou interessado em saber se alguém já definiu e estudou algum indicador estatístico que possa ser usado na definição de ou na determinação de outras propriedades gerais úteis de uma fórmula. Por indicador estatístico, quero dizer algo assim:r

  1. HCV (Contagem de Variância)

    Vamos ser uma função que, dada uma variável v jN , devolve o número de vezes de v j aparece em F . Vamos V ser o conjunto de variáveis usadas em F . Deixe ˉ h F = 1hF:NNvjNvjFVFser o AHC (Contagem Média Hit). O HCV é definido da seguinte forma: HVC=1h¯F=1|V|vjVhF(vj)

    Nos casos em aleatórios, o VHC é muito baixo (todas as variáveis são mencionados quase o mesmo número de vezes), enquanto que em casos estruturados não é (algumas variáveis são usados ​​com muita frequência e outros não, ou seja, existem "grupos de uso").HVC=1|V|vjV(hF(vj)h¯F)2





  2. hF+(vj)vjhF(vj)i:N[0,1]vjVi(vj) . Essas variáveis ​​que ocorrem metade das vezes positivas e metade das vezes negativas têm o Grau de Impureza máximo, enquanto as variáveis ​​sempre positivas ou sempre negativas (ou seja, literais puros) têm o Grau de Impureza mínimo. O AID é simplesmente definido da seguinte forma: AID=1i(vj)=2min(hF+(vj),hF(vj))hF(vj)

    Em instâncias aleatórias (pelo menos naquelas geradas pela negação de variáveis ​​com probabilidade0,5), o AID é quase igual a1, enquanto em casos estruturados geralmente está longe de1.AID=1|V|vjVi(vj)

    0.511

  3. IDV (Impurity Degree Variance)

    O IDV é um indicador mais robusto que o AID, pois é responsável por instâncias aleatórias geradas pela negação de variáveis ​​com probabilidade diferente de . É definido como: I D V = 10.5

    IDV=1|V|vjV(i(vj)AID)2

    00

Motivações

  1. Para entender melhor como as fórmulas da CNF funcionam, como sua aleatoriedade / estrutura pode ser medida, se outras propriedades gerais úteis puderem ser inferidas observando seus indicadores estatísticos, se e como esses indicadores podem ser usados ​​para acelerar a pesquisa.
  2. Pergunto-me se a satisfação (ou mesmo o número de soluções) de uma fórmula da CNF poderia ser inferida apenas manipulando com inteligência seus indicadores estatísticos.

Questões

  1. Alguém já propôs uma maneira de medir a aleatoriedade de uma fórmula da CNF?
  2. Alguém já propôs algum indicador estatístico que possa ser usado para estudar ou mesmo inferir mecanicamente propriedades gerais úteis de uma fórmula CNF?
Giorgio Camerani
fonte
1
consulte o documento nesta resposta ( cstheory.stackexchange.com/questions/4321/… ). Ele poderia dar-lhe uma dica sobre como definir tais r
Marcos Villagra
1
discussão possivelmente relevante sobre a medição da aleatoriedade de cadeias de bits mathoverflow.net/questions/37518/…
Yaroslav Bulatov
Eu posso lhe dizer isso desde que venho trabalhando nisso há um tempo. Se você considerar SAT, as fórmulas para 1 e 2 são exponenciais. Por outro lado, para k-SAT, as fórmulas para 1 e 2 são polinomiais. Isso se refere à minha DEFINIÇÃO PRECISA DE PERGUNTA ALEATÓRIA K-SAT, que ninguém parece querer responder.
Tayfun Pay
@ Geekster: Gostaria de fornecer uma resposta aqui?
Hsien-Chih Chang # 02/02
@ Geekster: O que você quer dizer com "... as fórmulas para 1 e 2 são exponenciais" ?
Giorgio Camerani 02/02

Respostas:

3

Sugiro emprestar à intuição física que estruturas "menos aleatórias" são mais simétricas. Simetria para CNF é qualquer transformação das variáveis, que mantém a função invariável. Por esse critério, funções de 3 variáveis ​​como

x1x2x3.

ou, digamos,

(x1x2¬x3)(x1¬x2x3)(¬x1x2x3)(¬x1¬x2¬x3).

são menos aleatórios do que, digamos

(x1x2¬x3)(x1¬x2x3)(¬x1¬x2x3).

Em geral, definir um conceito de "aleatório" em estruturas finitas é um desafio. Historicamente, foi testado em seqüências binárias, que são sem dúvida as estruturas finitas mais simples. Por exemplo, intuitivamente, uma sequência 01010101 é "menos aleatória" do que, digamos, 01001110. No entanto, foi rapidamente percebido que não há uma definição formal consistente de sequência aleatória finita ! Portanto, é preciso ser cético em relação a qualquer tentativa ingênua de definir uma medida de aleatoriedade para qualquer estrutura finita.

Tegiri Nenashi
fonte
Concordo totalmente com a intuição "estrutura significa presença de simetrias, enquanto aleatoriedade significa ausência de simetrias" . Você se refere a simetrias sintáticas (enquanto simetrias semânticas são aquelas que alteram a função, mas deixam o espaço da solução inalterado). Sempre estive convencido de que simetrias são a chave.
Giorgio Camerani 02/02
1
@ Walter: A idéia de simetrias é uma tentativa de alavancar a álgebra em vez de algoritmos: a complexidade algorítmica é uma medida que desafia a definição consistente de objetos finitos. Mas então temos que atribuir uma medida de complexidade a cada elemento de um grupo (por exemplo, a transformação que nega uma variável única é mais simples do que a que nega duas) - isso parece apenas empurrar o problema ...
Tegiri Nenashi