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

16

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 2n 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{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{0,1} für die es w1,,wnR+ so dass für alle v{0,1}n , wir haben f(v)=1 wenn f iwivi1?

Es ist nicht so schwer zu erkennen, dass nicht alle Funktionen so dargestellt werden können. Zum Beispiel kann die Funktion (x1x2)(x3x4) nicht: da (1,1,0,0) akzeptiert wird, müssen wir w1+w21 , also eines von w1,w2 muss 1/2 für und ebenso w3,w4 . Wenn es z. B.w1 undw3 , haben wir einen Widerspruch, weilw1+w31 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 k{0,1}nkk . 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.)

a3nm
quelle
Diese werden als Schwellenwertfunktionen bezeichnet (obwohl dieser Begriff manchmal restriktiver definiert wird). Ich weiß nicht, ob es eine wesentlich andere Charakterisierung gibt. Eine offensichtlich notwendige Bedingung ist, dass und f - 1 ( 0 ) konvex sind (das heißt, die konvexe Hülle von f - 1 ( 1 ), die sich mit { 0 , 1 } n schneidet , ist in f - 1 enthalten ( 1 ) und ähnlich für 0). f1(1)f1(0)f1(1){0,1}nf1(1)
Emil Jeřábek unterstützt Monica
Nun, da ich darüber nachdenke: Eine Boolesche Funktion ist eine Schwellenfunktion, wenn die konvexen Hüllen von f - 1 ( 1 ) und f - 1 ( 0 ) disjunkt sind. ff1(1)f1(0)
Emil Jeřábek unterstützt Monica
2
Tatsächlich sind dies genauer die positiven Schwellenfunktionen.
Kristoffer Arnsfelt Hansen
@KristofferArnsfeltHansen: Genau, danke! Tatsächlich wird dies in Booleschen Funktionen: Theorie, Algorithmen und Anwendungen erwähnt . Satz 9.16 besagt, dass wir bei einem positiven DNF in PTIME testen können, ob es sich um eine Schwellenwertfunktion handelt, und wenn ja, einen Vektor konstruieren können (der dann nach Satz 9.6 positiv sein wird, denke ich). Ist etwas über die von mir vorgeschlagenen Varianten bekannt, insbesondere die mit einer DAG für die Variablen? Wenn nicht, können Sie gerne eine Antwort geben, die dies sagt (und Ihren Kommentar zusammenfasst), und ich werde es akzeptieren. :)w
a3nm

Antworten:

2

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 ) = 1w1w2wn 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

f(v1,,vn)=1iwivi1.
(v1,,vn)f(v)=12n

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.fff(0,1,1)f(1,0,1)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

2,3,5,10,27,119,1113,
2,3,5,10,27,119,1173,
Bjørn Kjos-Hanssen
quelle
Vielen Dank! Ich möchte nur darauf hinweisen, dass die anderen Arten von Booleschen Funktionen, die in Ihrer Antwort genannt werden und deren Gesamtordnung den Einfluss von Variablen beeinflusst, als "reguläre" Boolesche Funktionen bezeichnet werden. Dies wird in der Sequenz A132183 erwähnt, und solche Funktionen werden in Kapitel 8 der Booleschen Funktionen: Theorie, Algorithmen und Anwendungen
a3nm