Mesurer le caractère aléatoire des formules CNF

12

Il est bien connu que les formules CNF peuvent être grossièrement partitionnées en 2 grandes classes: aléatoire vs structurée. Les formules CNF structurées, contrairement aux formules CNF aléatoires, présentent une sorte d'ordre, montrant des modèles qui ne se produiront probablement pas par hasard. Cependant, on peut trouver des formules structurées montrant un certain degré de caractère aléatoire (c'est-à-dire que certains groupes spécifiques de clauses semblent beaucoup moins structurés que d'autres), ainsi que des formules aléatoires avec une certaine forme de structure faible (c'est-à-dire que certains groupes spécifiques de clauses semblent moins aléatoires que d'autres ). Il semble donc que le caractère aléatoire d'une formule ne soit pas simplement un fait oui / non.

Soit une fonction qui, étant donnée une formule CNF F F , renvoie une valeur réelle comprise entre 0 et 1 inclus: 0 signifie une formule structurée pure, tandis que 1 signifie une formule aléatoire pure.r:F[0,1]FF0101

Je me demande si quelqu'un a déjà essayé d'inventer un tel . Bien sûr, la valeur retournée par r ne serait (du moins c'est mon intention) qu'une mesure pratique selon certains critères raisonnables, plutôt qu'une solide vérité théorique.rr

Je suis également intéressé de savoir si quelqu'un a déjà défini et étudié un indicateur statistique pouvant être utilisé dans la définition de ou dans la détermination d'autres propriétés globales utiles d'une formule. Par indicateur statistique, je veux dire quelque chose comme ça:r

  1. VHC (Compteur Variance)

    Soit une fonction qui, étant donné une variable v jN , retourne le nombre de fois v j apparaît dans F . Laissez - V l'ensemble des variables utilisées dans F . Soit ˉ h F = 1hF:NNvjNvjFVFêtre le AHC (Average Hit Count). Le VHC est défini comme suit: HVC=1h¯F=1|V|vjVhF(vj)

    Dans les cas aléatoires, le VHC est très faible (toutes les variables sont mentionnées presque le même nombre de fois), tandis que dans les cas structurés, il ne l'est pas (certaines variables sont utilisées très fréquemment et d’autres pas, c’est-à-dire qu’il existe des «grappes d’utilisation»).HVC=1|V|vjV(hF(vj)h¯F)2



  2. AID (Moyenne Impureté degré)

    Soit soit le nombre de fois v j se produit positif, et laisser h - F ( v j ) le nombre de fois où il se produit négatif. Soit i : N[ 0 , 1 ] une fonction qui, étant donnée une variable v jV , renvoie son ID (degré d'impureté). La fonction i ( v j ) est définie comme suit: i (hF+(vj)vjhF(vj)i:N[0,1]vjVi(vj) . Ces variables se produisant la moitié des fois positives et la moitié des fois négatives ont un degré d'impureté maximum, tandis que ces variables se produisant toujours positives ou toujours négatives (c'est-à-dire des littéraux purs) ont un degré d'impureté minimum. L'AID est simplement défini comme suit: AID=1i(vj)=2min(hF+(vj),hF(vj))hF(vj)

    Dans les cas aléatoires (au moins dans ceux générés par des variables négatives avec une probabilité de0,5), l'AID est presque égal à1, tandis que dans les cas structurés, il est généralement loin de1.AID=1|V|vjVi(vj)

    0.511

  3. IDV (Impurity Degree Variance)

    L'IDV est un indicateur plus robuste que l'AID seul, car il tient compte des instances aléatoires générées par la négation des variables avec une probabilité différente de . Il est défini comme suit: I D V = 10.5

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

    00

Les motivations

  1. Pour mieux comprendre le fonctionnement des formules CNF, comment leur caractère aléatoire / structure pourrait être mesuré, si d'autres propriétés globales utiles pouvaient être déduites en examinant leurs indicateurs statistiques, si et comment ces indicateurs pourraient être utilisés pour accélérer la recherche.
  2. Je me demande si la satisfiabilité (ou même le nombre de solutions) d'une formule CNF pourrait être déduite en manipulant simplement habilement ses indicateurs statistiques.

Des questions

  1. Quelqu'un a-t-il déjà proposé un moyen de mesurer le caractère aléatoire d'une formule CNF?
  2. Quelqu'un a-t-il déjà proposé un indicateur statistique pouvant être utilisé pour étudier ou même déduire mécaniquement les propriétés globales utiles d'une formule CNF?
Giorgio Camerani
la source
1
voir l'article dans cette réponse ( cstheory.stackexchange.com/questions/4321/… ). Il pourrait vous donner une astuce sur la façon de définir un tel r
Marcos Villagra
1
discussion peut-être pertinente sur la mesure du caractère aléatoire des chaînes binaires mathoverflow.net/questions/37518/…
Yaroslav Bulatov
Je peux vous en dire beaucoup depuis que je travaille sur ce sujet depuis un certain temps. Si vous considérez SAT, les formules pour 1 et 2 sont exponentielles. En revanche pour k-SAT les formules pour 1 & 2 sont polynomiales. Cela concerne ma DÉFINITION PRÉCISE DE LA QUESTION ALÉATOIRE K-SAT, à laquelle personne ne semble vouloir répondre.
Tayfun Pay du
@Geekster: Souhaitez-vous fournir une réponse ici?
Hsien-Chih Chang 張顯 之
@Geekster: Que voulez-vous dire par "... les formules pour 1 et 2 sont exponentielles" ?
Giorgio Camerani

Réponses:

3

Je suggère d'emprunter l'intuition physique que les structures "moins aléatoires" sont plus symétriques. La symétrie pour CNF est toute transformation des variables, qui maintient la fonction invariante. Par ce critère, les fonctions de 3 variables telles que

x1x2x3.

ou, disons,

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

sont moins aléatoires que, disons

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

En général, définir un concept de "aléatoire" sur des structures finies est difficile. Historiquement, il a été essayé sur des séquences binaires, qui sont sans doute les structures finies les plus simples. Par exemple, intuitivement, une séquence 01010101 est "moins aléatoire" que, disons, 01001110. Cependant, on s'est vite rendu compte qu'il n'y a pas de définition formelle cohérente d' une séquence aléatoire finie ! Par conséquent, il faut être sceptique vis-à-vis de toute tentative naïve de définir une mesure de caractère aléatoire pour toute structure finie.

Tegiri Nenashi
la source
Je suis totalement d'accord avec l'intuition "la structure signifie la présence de symétries, tandis que le hasard signifie l'absence de symétries" . Vous faites référence aux symétries syntaxiques (alors que les symétries sémantiques sont celles qui modifient la fonction mais ne modifient pas l'espace de la solution). J'ai toujours été convaincu que les symétries sont la clé.
Giorgio Camerani
1
@Walter: L'idée de symétries est une tentative de tirer parti de l'algèbre plutôt que des algorithmes: la complexité algorithmique est une mesure qui défie la définition cohérente des objets finis. Mais ensuite, nous devons attribuer une mesure de complexité à chaque élément d'un groupe (par exemple, la transformation qui nie une seule variable est plus simple que celle qui en nie deux) - cela ressemble à simplement pousser le problème ...
Tegiri Nenashi