Welche monotonen Booleschen Funktionen sind als Schwellenwerte für Summen darstellbar?

Ich werde mein Problem mit einem Beispiel vorstellen. Angenommen, Sie entwerfen eine Prüfung, die aus einer bestimmten Menge von $n$ unabhängigen Fragen besteht (die die Kandidaten entweder richtig oder falsch beantworten können). Sie möchten sich für eine Punktzahl entscheiden, die für jede der Fragen vergeben werden soll. Dabei gilt die Regel, dass Kandidaten mit einer Gesamtpunktzahl über einem bestimmten Schwellenwert bestehen und die anderen nicht bestehen.

Tatsächlich sind Sie sehr gründlich und haben sich alle möglichen $2^n$ Ergebnisse vorgestellt und für jeden von ihnen entschieden, ob ein Kandidat mit dieser Leistung bestehen oder scheitern sollte. Sie haben also eine Boolesche Funktion $f : \{0, 1\}^n \to \{0, 1\}$ , die angibt, ob der Kandidat in Abhängigkeit von seinen genauen Antworten bestehen oder scheitern sollte. Natürlich sollte diese Funktion eintönig sein : Wenn Sie eine Reihe von Fragen als richtig ansehen, müssen Sie auch eine Übermenge als richtig ansehen.

Können Sie Punkte (positive reelle Zahlen) für die Fragen und einen Schwellenwert festlegen, sodass Ihre Funktion $f$ genau von der Regel erfasst wird , dass ein Kandidat besteht, wenn die Summe der Punkte für die richtigen Fragen über dem Schwellenwert liegt? ? (Natürlich kann der Schwellenwert ohne Verlust der Allgemeinheit als 1 angenommen werden, bis die Punktzahlen mit einer Konstanten multipliziert werden.)

Formal: Gibt es eine Charakterisierung der monotonen Booleschen Funktionen $f: \{0, 1\}^n \to \{0, 1\}$ für die es $w_1, \ldots, w_n \in \mathbb{R}_+$ so dass für alle $v \in \{0, 1\}^n$ , wir haben $f(v) = 1$ wenn f $\sum_i w_i v_i \geq 1$?

Es ist nicht so schwer zu erkennen, dass nicht alle Funktionen so dargestellt werden können. Zum Beispiel kann die Funktion $(x_1 \wedge x_2) \vee (x_3 \wedge x_4)$ nicht: da $(1, 1, 0, 0)$ akzeptiert wird, müssen wir $w_1 + w_2 \geq 1$ , also eines von $w_1, w_2$ muss $\geq 1/2$ für und ebenso $w_3, w_4$ . Wenn es z. B.$w_1$ und$w_3$ , haben wir einen Widerspruch, weil$w_1 + w_3 \geq 1$ aber$(1, 0, 1, 0)$ abgelehnt wird; Die anderen Fälle sind analog.

Dies scheint mir ein sehr natürliches Problem zu sein, daher ist meine Hauptfrage zu wissen, unter welchem ​​Namen dies untersucht wurde. Nach einer "Charakterisierung" zu fragen, ist natürlich vage; Meine Frage ist zu wissen, ob die Klasse von Funktionen, die auf diese Weise dargestellt werden können, einen Namen hat, was über die Komplexität des Testens, ob eine Eingabefunktion zu ihr gehört (gegeben als Formel oder als Schaltung) usw. bekannt ist.

Natürlich kann man sich viele Variationen zu diesem Thema vorstellen. Beispielsweise sind Fragen zu realen Prüfungen nicht unabhängig, aber es gibt eine DAG zu Fragen, die auf die Abhängigkeit hinweisen, und Kandidaten können eine Frage nur beantworten, wenn alle Voraussetzungen erfüllt sind. Die Bedingung für die monotonen Funktionen könnte dann auf Bewertungen in , die die Abhängigkeiten erfüllen, und die Frage wäre zu bestimmen, ob eine Eingabefunktion auf diese Weise bei einer Eingabe-DAG für die Variablen erfasst werden kann. Man könnte sich auch Varianten vorstellen, bei denen die Scores k- Tupel für festes k sind (punktweise summiert und punktweise mit einem Schwellenvektor verglichen), die mehr Funktionen erfassen können als $\{0, 1\}^n$$k$$k$ . Alternativ können Sie aussagekräftigere Funktionen erfassen, die nicht boolesch sind, sondern zu einer vollständig geordneten Domäne gehören, mit unterschiedlichen Schwellenwerten, die Ihre Position in der Domäne angeben sollen. Zuletzt bin ich mir nicht sicher, was passieren würde, wenn Sie negative Scores zulassen (sodass Sie die monotone Einschränkung für die Funktionen aufheben könnten).$k = 1$

(Hinweis: Ich habe mich über die Auswahlrunde von Google Code Jam gewundert, in der Kandidaten ausgewählt werden, wenn sie eine bestimmte Bewertungsschwelle erreichen. Vermutlich werden die Punktzahlen der Probleme sorgfältig ausgearbeitet, um zu reflektieren, welche Problemgruppen als ausreichend für die Auswahl angesehen werden Code Jam hat eine Abhängigkeitsstruktur von den Fragen, mit einigen "großen Eingaben", die nicht gelöst werden können, es sei denn, Sie haben die "kleinen Eingaben" zuerst gelöst.)

In den Kommentaren wurde erwähnt, dass dies die positiven Schwellenfunktionen sind.

Was andere Charakterisierungen betrifft, fand ich Folgendes interessant. Angenommen, wir haben eine positive Schwellenfunktion mit abnehmenden Gewichten : f ( v 1 , … , v n ) = $w_1\ge w_2\ge\dots w_n$ Dann ist insbesondere die Menge der Eingänge(v1,…,vn),für dief( → v )=1ist, ein Ordnungsideal des binären Majorisierungsgitters mit2nPunkten, das heißt studierte in

Donald Knuth, "Die Kunst der Computerprogrammierung", Übung 109 von Abschnitt 7.1.1.

Um es informell zu setzen, ist die Art der Funktion , wo früher die Bits 1 Marken machen f eher zu 1: so zB f ( 0 , 1 , 1 ) ≤ f ( 1 , 0 , 1 ) ≤ f ( 1 , 1 , 0 ) . Das heißt, "einige Bits sind wichtiger", und um redundante isomorphe Fälle zu entfernen, nehmen wir an, dass frühere Bits wichtiger sind.$f$$f$$f(0,1,1)\le f(1,0,1)\le f(1,1,0)$

Es sind jedoch nicht alle dieser Funktionen positive Schwellenfunktionen! Das heißt, nur weil Sie die Prüfungsfragen von den wichtigsten bis zu den wenigsten Fragen geordnet haben, bedeutet dies nicht, dass Ihre Bestehen- / Nichtbestehen-Regel darauf basiert, nur einige Punkte zu addieren.

$n$