Quelles fonctions booléennes monotones sont représentables comme seuils sur les sommes?

Je vais présenter mon problème avec un exemple. Supposons que vous concevez un examen, qui consiste en un certain ensemble de questions indépendantes (que les candidats peuvent avoir raison ou tort). Vous voulez décider d'un score à attribuer à chacune des questions, la règle étant que les candidats ayant un score total supérieur à un certain seuil passeront et que les autres échoueront.$n$

En fait, vous êtes très consciencieux à ce sujet, et vous avez envisagé tous les résultats possibles, et décidé pour chacun d'eux si un candidat avec cette performance devait réussir ou échouer. Vous avez donc une fonction booléenne qui indique si le candidat doit réussir ou échouer en fonction de ses réponses exactes. Bien sûr, cette fonction doit être monotone : lorsque vous obtenez un ensemble de questions correctes, vous devez réussir tout autre sur-ensemble.$2^n$$f : \{0, 1\}^n \to \{0, 1\}$

Pouvez-vous décider des scores (nombres réels positifs) à attribuer aux questions et d'un seuil, de sorte que votre fonction soit exactement capturée par la règle "un candidat réussit si la somme des scores pour les bonnes questions est supérieure au seuil" ? (Bien sûr, le seuil peut être considéré comme 1 sans perte de généralité, jusqu'à multiplier les scores par une constante.)$f$

Formellement: existe-t-il une caractérisation des fonctions booléennes monotones pour lesquelles il existe de telle sorte que pour toutw 1 , … , w n ∈ R + v ∈ { 0 , 1 } $f: \{0, 1\}^n \to \{0, 1\}$$w_1, \ldots, w_n \in \mathbb{R}_+$$v \in \{0, 1\}^n$ , on a ssi Σ i w i v i ≥ 1 ?$f(v) = 1$$\sum_i w_i v_i \geq 1$

Il n'est pas si difficile de voir que toutes les fonctions ne peuvent pas être ainsi représentées. Par exemple, la fonction ne peut pas: comme ( 1 , 1 , 0 , 0 ) est acceptée, nous devons avoir w 1 + w 2 ≥ 1 , donc l'un de w 1 , w 2 doit être ≥ une / 2 , et de même pour w 3$(x_1 \wedge x_2) \vee (x_3 \wedge x_4)$$(1, 1, 0, 0)$$w_1 + w_2 \geq 1$$w_1, w_2$$\geq 1/2$ . Maintenant, si elle est, par exemple, w 1 et w 3 , nous avons une contradiction parce que w 1 + w 3 ≥ 1 mais ( 1 , 0 , 1 , 0 ) est rejetée; les autres cas sont analogues.$w_3, w_4$$w_1$$w_3$$w_1 + w_3 \geq 1$$(1, 0, 1, 0)$

Cela me semble être un problème très naturel, donc ma principale question est de savoir sous quel nom cela a été étudié. Bien entendu, demander une "caractérisation" est vague; ma question est de savoir si la classe de fonctions qui peut être représentée de cette façon a un nom, ce que l'on sait de la complexité du test pour savoir si une fonction d'entrée lui appartient (donnée sous forme de formule ou de circuit), etc.

Bien sûr, on peut penser à de nombreuses variantes sur ce thème. Par exemple, sur de vrais examens, les questions ne sont pas indépendantes, mais il existe un DAG sur les questions indiquant la dépendance, et les candidats ne peuvent répondre à une question que si toutes les conditions préalables ont été remplies. La condition sur les fonctions monotones pourrait alors être limitée aux évaluations dans qui satisfont les dépendances, et la question serait de déterminer si une fonction d'entrée peut être ainsi capturée étant donné un DAG d'entrée sur les variables. On pourrait également penser à des variantes où les scores sont k -uples pour k fixe (sommés ponctuellement et comparés ponctuellement à un vecteur de seuil), qui peuvent capturer plus de fonctions que $\{0, 1\}^n$$k$$k$ . Alternativement, vous pouvez vouloir capturer des fonctions plus expressives qui ne sont pas booléennes mais aller vers un domaine totalement ordonné, avec différents seuils qui devraient indiquer votre position dans le domaine. Enfin, je ne suis pas sûr de ce qui se passerait si vous autorisez des scores négatifs (vous pouvez donc supprimer la restriction monotone concernant les fonctions).$k = 1$

(Remarque: ce qui m'a amené à me poser des questions à ce sujet, c'est le tour de sélection de Google Code Jam, où les candidats sont sélectionnés s'ils atteignent un certain seuil de score, et les scores de problèmes sont probablement conçus avec soin pour refléter quels ensembles de problèmes sont jugés suffisants pour être sélectionnés. . Code Jam a une structure de dépendance sur les questions, avec certaines questions "à grande entrée" qui ne peuvent pas être résolues à moins que vous ayez résolu la "petite entrée" une première.)

Il a été mentionné dans les commentaires que ce sont les fonctions de seuil positif.

Quant aux autres caractérisations, j'ai trouvé les suivantes intéressantes. Supposons que nous ayons une fonction de seuil positive avec des poids décroissants : f ( v 1 , … , v n ) = $w_1\ge w_2\ge\dots w_n$ Puis en particulier l'ensemble des entrées(v1,…,

Donald Knuth, «L'art de la programmation informatique», exercice 109 de la section 7.1.1.

Pour le dire de manière informelle, est le type de fonction où le fait de faire des bits antérieurs 1 rend f plus probable d'être 1: donc par exemple f ( 0 , 1 , 1 ) ≤ f ( 1 , 0 , 1 ) ≤ f ( 1 , 1 , 0 ) . Autrement dit, "certains bits importent plus", et pour supprimer les cas isomorphes redondants, nous supposons que les bits antérieurs importent plus.$f$$f$$f(0,1,1)\le f(1,0,1)\le f(1,1,0)$

Cependant, toutes ces fonctions ne sont pas des fonctions à seuil positif! C'est-à-dire que le fait que vous ayez commandé les questions d'examen du plus important au moins ne signifie pas que votre règle de réussite / échec est basée sur la simple addition de certains scores.

En effet, le nombre de fonctions de seuil positives (avec des poids décroissants) sur variables est donné par la séquence 2 , 3 , 5 , 10 , 27 , 119 , 1113 , … (séquence oeis.org A000617 ) alors que le nombre de tels idéaux d'ordre est 2 , 3 , 5 , 10 , 27 , 119 , 1173 , … (séquence oeis.org A132183 )$n$