¿Qué funciones booleanas monótonas son representables como umbrales en sumas?

Introduciré mi problema con un ejemplo. Supongamos que está diseñando un examen, que consiste en un cierto conjunto de preguntas independientes (que los candidatos pueden obtener bien o mal) Desea decidir sobre un puntaje para dar a cada una de las preguntas, con la regla de que los candidatos con puntaje total por encima de un cierto umbral pasarán y los demás fallarán.$n$

De hecho, usted es muy minucioso al respecto, y ha previsto todos los resultados posibles , y ha decidido para cada uno de ellos si un candidato con este desempeño debe aprobar o no. Entonces tiene una función booleana que indica si el candidato debe aprobar o reprobar dependiendo de sus respuestas exactas. Por supuesto, esta función debe ser monótona : cuando acertar un conjunto de preguntas te hace aprobar, obtener un superconjunto correcto también debe hacerte pasar. f : { 0 , 1 } n → { 0 , 1 $2^n$$f : \{0, 1\}^n \to \{0, 1\}$

¿Puede decidir sobre los puntajes (números reales positivos) para dar a las preguntas y en un umbral, de modo que su función sea ​​capturada exactamente por la regla "un candidato pasa si la suma de puntajes para las preguntas correctas está por encima del umbral" ? (Por supuesto, el umbral puede tomarse como 1 sin pérdida de generalidad, hasta multiplicar los puntajes por una constante).$f$

Formalmente: ¿Existe una caracterización de las funciones booleanas monótonas para las cuales existen tal que para todos , tenemos iff ?w 1 , … , w n ∈ R + v ∈ { 0 , 1 } n f ( v ) = 1 ∑ i w i v i ≥ $f: \{0, 1\}^n \to \{0, 1\}$$w_1, \ldots, w_n \in \mathbb{R}_+$$v \in \{0, 1\}^n$$f(v) = 1$$\sum_i w_i v_i \geq 1$

No es tan difícil ver que no todas las funciones pueden representarse así. Por ejemplo, la función no puede: como es aceptado, debemos tener , entonces uno de debe ser , y del mismo modo para . Ahora, si es, por ejemplo, y , tenemos una contradicción porque pero se rechaza; Los otros casos son análogos.( 1 , 1 , 0 , 0 ) w 1 + w 2 ≥ 1 w 1 , w 2 ≥ 1 / 2 w 3 , w 4 w 1 w 3 w 1 + w 3 ≥ 1 ( 1 , 0 $(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$$w_3, w_4$$w_1$$w_3$$w_1 + w_3 \geq 1$$(1, 0, 1, 0)$

Esto me parece un problema muy natural, por lo que mi pregunta principal es saber con qué nombre se ha estudiado. Pedir una "caracterización" es vago, por supuesto; mi pregunta es saber si la clase de funciones que se pueden representar de esta manera tiene un nombre, qué se sabe sobre la complejidad de probar si una función de entrada le pertenece (dada como una fórmula o como un circuito), etc.

Por supuesto, uno puede pensar en muchas variaciones sobre este tema. Por ejemplo, en los exámenes reales, las preguntas no son independientes, pero hay un DAG en las preguntas que indican la dependencia, y los candidatos solo pueden responder una pregunta si se han respondido todos los requisitos previos. La condición en las funciones monótonas podría entonces restringirse a valoraciones en que satisfagan las dependencias, y la pregunta sería determinar si una función de entrada puede ser capturada de esta manera dado un DAG de entrada en las variables. También se podría pensar en variantes donde los puntajes son -tuplas para fijo (sumado puntual y comparado puntual a un vector umbral), que pueden capturar más funciones que$\{0, 1\}^n$$k$$k$$k = 1$. Alternativamente, podría querer capturar funciones más expresivas que no sean booleanas pero que vayan a un dominio totalmente ordenado, con diferentes umbrales que deberían indicar su posición en el dominio. Por último, no estoy seguro de lo que sucedería si permitiera puntuaciones negativas (por lo que podría eliminar la restricción monótona sobre las funciones).

(Nota: lo que me hizo preguntarme sobre esto es la ronda de selección de Google Code Jam, donde se seleccionan los candidatos si alcanzan un cierto umbral de puntaje, y los puntajes de los problemas están presumiblemente diseñados cuidadosamente para reflejar qué conjuntos de problemas se consideran suficientes para ser seleccionados Code Jam tiene una estructura de dependencia en las preguntas, con algunas preguntas de "entrada grande" que no se pueden resolver a menos que usted haya resuelto primero la "entrada pequeña".

En los comentarios se mencionó que estas son las funciones de umbral positivo.

$w_1\ge w_2\ge\dots w_n$

Donald Knuth, "El arte de la programación de computadoras", ejercicio 109 de la sección 7.1.1.

$f$$f$$f(0,1,1)\le f(1,0,1)\le f(1,1,0)$

Sin embargo, ¡no todas esas funciones son funciones de umbral positivo! Es decir, el hecho de que haya ordenado las preguntas del examen de la más importante a la menos no significa que su regla de aprobación / reprobación se base simplemente en sumar algunas puntuaciones.

$n$