Fungsi Boolean monoton mana yang direpresentasikan sebagai ambang jumlah?

Saya akan memperkenalkan masalah saya dengan sebuah contoh. Katakanlah Anda sedang merancang sebuah ujian, yang terdiri dari satu set tertentu dari $n$ pertanyaan independen (bahwa calon bisa mendapatkan benar atau salah). Anda ingin memutuskan skor untuk diberikan pada masing-masing pertanyaan, dengan aturan bahwa calon dengan skor total di atas ambang tertentu akan lulus, dan yang lainnya akan gagal.

Bahkan, Anda sangat teliti tentang hal ini, dan Anda telah membayangkan segala kemungkinan $2^n$ hasil, dan memutuskan untuk masing-masing apakah calon dengan kinerja ini harus lulus atau gagal. Jadi Anda memiliki fungsi Boolean $f : \{0, 1\}^n \to \{0, 1\}$ yang menunjukkan apakah kandidat harus lulus atau gagal tergantung pada jawaban yang tepat. Tentu saja fungsi ini harus monoton : ketika mendapatkan serangkaian pertanyaan yang benar membuat Anda lulus, mendapatkan superset yang benar harus membuat Anda lulus juga.

Bisakah Anda memutuskan skor (bilangan real positif) untuk diberikan pada pertanyaan, dan pada ambang, sehingga fungsi Anda $f$ benar-benar ditangkap oleh aturan "seorang kandidat lulus jika jumlah skor untuk pertanyaan yang benar berada di atas ambang" ? (Tentu saja ambang dapat dianggap 1 tanpa kehilangan keumuman, hingga mengalikan skor dengan konstanta.)

Secara formal: Apakah ada karakterisasi fungsi monoton Boolean yang ada sedemikian rupa sehingga untuk semua , kita memiliki 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$

Tidak terlalu sulit untuk melihat bahwa tidak semua fungsi dapat diwakili. Misalnya fungsi tidak dapat: karena diterima, kita harus memiliki w 1 + w 2 ≥ 1 , jadi salah satu dari w 1 , w 2 harus , dan juga untuk . Sekarang, jika ya, misalnya, dan , kami memiliki kontradiksi karena tetapi ditolak; kasus-kasus lainnya analog.$(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)$

Bagi saya ini terlihat seperti masalah yang sangat alami, jadi pertanyaan utama saya adalah mengetahui dengan nama apa ini telah dipelajari. Meminta "karakterisasi" tidak jelas, tentu saja; pertanyaan saya adalah untuk mengetahui apakah kelas fungsi yang dapat direpresentasikan dengan cara ini memiliki nama, apa yang diketahui tentang kerumitan pengujian apakah fungsi input miliknya (diberikan sebagai rumus, atau sebagai sirkuit), dll.

Tentu saja orang dapat memikirkan banyak variasi pada tema ini. Misalnya, pada ujian nyata, pertanyaan tidak independen, tetapi ada DAG pada pertanyaan yang menunjukkan ketergantungan, dan kandidat hanya dapat menjawab pertanyaan jika semua prasyarat telah dijawab. Kondisi pada fungsi monoton kemudian dapat dibatasi pada penilaian dalam yang memenuhi dependensi, dan pertanyaannya adalah menentukan apakah fungsi input dapat ditangkap dengan diberi input DAG pada variabel. Kita juga bisa memikirkan varian di mana skornya adalah -tuples untuk fixed (dijumlahkan secara pointwise, dan dibandingkan secara pointwise dengan vektor threshold), yang dapat menangkap lebih banyak fungsi daripada k k k = $\{0, 1\}^n$$k$$k$$k = 1$. Atau Anda dapat menangkap fungsi yang lebih ekspresif yang bukan Boolean tetapi buka domain yang benar-benar dipesan, dengan ambang batas berbeda yang akan menunjukkan posisi Anda di domain. Terakhir, saya tidak yakin tentang apa yang akan terjadi jika Anda mengizinkan skor negatif (sehingga Anda dapat menjatuhkan batasan monoton tentang fungsi).

(Catatan: Apa yang membuat saya bertanya-tanya tentang ini adalah putaran pemilihan Google Code Jam, di mana kandidat dipilih jika mereka mencapai batas skor tertentu, dan skor masalah mungkin dirancang dengan hati-hati untuk mencerminkan set masalah yang dianggap cukup untuk dipilih). Code Jam memiliki struktur ketergantungan pada pertanyaan, dengan beberapa pertanyaan "input besar" yang tidak dapat diselesaikan kecuali Anda telah memecahkan "input kecil" yang pertama.)

Disebutkan dalam komentar bahwa ini adalah fungsi ambang positif.

Adapun penokohan lainnya, saya menemukan yang berikut ini menarik. Misalkan kita memiliki fungsi threshold positif dengan penurunan bobot : f ( v 1 , ... , v n ) = $w_1\ge w_2\ge\dots w_n$ Kemudian secara khusus set input(v1,…,vn)yangf( → v )=1adalah ideal urutan kisi mayorisasi biner dengan2npoin, yaitu belajar di

Donald Knuth, "Seni Pemrograman Komputer", Latihan 109 dari Bagian 7.1.1.

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

Namun, tidak semua fungsi tersebut adalah fungsi ambang positif! Yaitu, hanya karena Anda telah memesan soal-soal ujian dari yang paling penting hingga yang paling tidak berarti aturan lulus / gagal Anda didasarkan hanya dengan menjumlahkan beberapa skor.

$n$