Jakie monotoniczne funkcje boolowskie są reprezentowane jako progi sum?

Przedstawię mój problem na przykładzie. Powiedzmy, że projektujesz egzamin, który składa się z pewnego zestawu niezależnych pytań (że kandydaci mogą mieć rację albo dobrze). Chcesz zdecydować o wyniku dla każdego pytania, z tą regułą, że kandydaci z całkowitą liczbą punktów powyżej pewnego progu przejdą, a pozostałe zawiodą.$n$

W rzeczywistości jesteś bardzo dokładny i przewidziałeś wszystkie możliwe wyników i dla każdego z nich zdecydowałeś, czy kandydat z takim występem powinien zaliczyć, czy nie. Mamy więc funkcję boolowską f : { 0 , 1 } n → { 0 , 1 }, która wskazuje, czy kandydat powinien zaliczyć, czy nie, w zależności od dokładnych odpowiedzi. Oczywiście ta funkcja powinna być monotonna : kiedy uzyskanie prawidłowego zestawu pytań powoduje, że zdajesz, uzyskanie odpowiedniego prawa superset musi również zdać.$2^n$$f : \{0, 1\}^n \to \{0, 1\}$

Czy możesz zdecydować o wynikach (dodatnich liczbach rzeczywistych), które należy podać w pytaniach, oraz o wartości progowej, aby twoja funkcja została dokładnie ujęta przez zasadę „kandydat przechodzi, jeśli suma wyników dla prawidłowych pytań jest powyżej progu” ? (Oczywiście próg można przyjąć jako 1 bez utraty ogólności, aż do pomnożenia wyników przez stałą.)$f$

Formalnie: czy istnieje charakterystyka monotonicznych funkcji boolowskich dla których istnieją w 1 , … , w n ∈ R +, tak że dla wszystkich v ∈ { 0 , 1 } n , mamy f ( v ) = 1 iff ∑ i w i v $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$?

Nietrudno zauważyć, że nie wszystkie funkcje mogą być w ten sposób reprezentowane. Na przykład funkcja nie może: ponieważ ( 1 , 1 , 0 , 0 ) jest akceptowana, musimy mieć w 1 + w 2 ≥ 1 , więc jedno z w 1 , w 2 musi być ≥ 1 / 2 , i podobnie 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$$w_3, w_4$. Teraz, jeśli jest np. i w 3 , mamy sprzeczność, ponieważ w 1 + w 3 ≥ 1 ale ( 1 , 0 , 1 , 0 $w_1$$w_3$$w_1 + w_3 \geq 1$$(1, 0, 1, 0)$ jest odrzucone; pozostałe przypadki są analogiczne.

To wydaje mi się bardzo naturalnym problemem, więc moim głównym pytaniem jest wiedzieć, pod jaką nazwą to zbadano. Pytanie o „charakterystykę” jest oczywiście niejasne; moim pytaniem jest wiedzieć, czy klasa funkcji, które mogą być reprezentowane w ten sposób, ma nazwę, co wiadomo o złożoności testowania, czy należy do niej funkcja wejściowa (podana jako formuła, czy jako obwód) itp.

Oczywiście można pomyśleć o wielu odmianach tego tematu. Na przykład na prawdziwych egzaminach pytania nie są niezależne, ale DAG dotyczy pytań wskazujących na zależność, a kandydaci mogą odpowiedzieć na pytanie tylko wtedy, gdy zostaną spełnione wszystkie warunki wstępne. Warunek funkcji monotonicznych można by wówczas ograniczyć do wycen w które spełniają zależności, a pytaniem byłoby ustalić, czy można w ten sposób uchwycić funkcję wejściową, biorąc pod uwagę wejściowy DAG dla zmiennych. Można również pomyśleć o wariantach, w których wyniki są k -tu dla stałej k (sumowane punktowo i porównywane punktowo z wektorem progowym), które mogą uchwycić więcej funkcji niż $\{0, 1\}^n$$k$$k$$k = 1$. Alternatywnie możesz uchwycić bardziej ekspresyjne funkcje, które nie są logiczne, ale przechodzą do całkowicie uporządkowanej domeny, z różnymi progami, które powinny wskazywać Twoją pozycję w domenie. Wreszcie, nie jestem pewien, co by się stało, gdybyś dopuścił ujemne wyniki (abyś mógł zrezygnować z monotonicznego ograniczenia funkcji).

(Uwaga: zastanawiałem się nad tym, to runda selekcji Google Code Jam, w której kandydaci są wybierani, jeśli osiągną określony próg punktowy, a wyniki problemów są prawdopodobnie starannie opracowane, aby odzwierciedlić, które zestawy problemów uznaje się za wystarczające do wybrania Code Jam ma strukturę zależności od pytań, z niektórymi pytaniami „dużego wkładu”, których nie można rozwiązać, chyba że najpierw rozwiązałeś „małe wejście”).

W komentarzach wspomniano, że są to funkcje progu dodatniego.

Jeśli chodzi o inne cechy, uważam, że następujące są interesujące. Załóżmy, że mamy dodatnią funkcję progową ze zmniejszającymi się ciężarami : f ( v 1 , … , v n ) = $w_1\ge w_2\ge\dots w_n$ W szczególności zbiór danych wejściowych(v1,…,vn),dla którychf( → v )=1jest ideałem porządku sieci binarnej z2npunktami, czyli studiował w

Donald Knuth, „Sztuka programowania komputerowego”, ćwiczenie 109 z rozdziału 7.1.1.

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

Jednak nie wszystkie takie funkcje są dodatnimi funkcjami progowymi! To dlatego, że uporządkowałeś pytania egzaminacyjne od najważniejszych do najmniej ważnych, nie oznacza, że ​​twoja reguła zaliczenia / zaliczenia polega na dodaniu kilku punktów.

$n$