16
$\begingroup$

I will introduce my problem with an example. Say you are designing an exam, which consists of a certain set of $n$ independent questions (that the candidates can get either right or wrong). You want to decide on a score to give to each of the questions, with the rule being that candidates with total score above a certain threshold will pass, and the others will fail.

In fact, you are very thorough about this, and you have envisioned all the possible $2^n$ results, and decided for each of them whether a candidate with this performance should pass or fail. So you have a Boolean function $f : \{0, 1\}^n \to \{0, 1\}$ that indicates whether the candidate should pass or fail depending on their exact answers. Of course this function should be monotone: when getting a set of questions right makes you pass, getting any superset right must make you pass as well.

Can you decide on scores (positive real numbers) to give to the questions, and on a threshold, so that your function $f$ is exactly captured by the rule "a candidate passes if the sum of scores for the correct questions is above the threshold"? (Of course the threshold can be taken to be 1 without loss of generality, up to multiplying the scores by a constant.)

Formally: Is there a characterization of the monotone Boolean functions $f: \{0, 1\}^n \to \{0, 1\}$ for which there exist $w_1, \ldots, w_n \in \mathbb{R}_+$ such that for all $v \in \{0, 1\}^n$, we have $f(v) = 1$ iff $\sum_i w_i v_i \geq 1$?

It is not so hard to see that not all functions can be thus represented. For instance the function $(x_1 \wedge x_2) \vee (x_3 \wedge x_4)$ cannot: as $(1, 1, 0, 0)$ is accepted we must have $w_1 + w_2 \geq 1$, so one of $w_1, w_2$ must be $\geq 1/2$, and likewise for $w_3, w_4$. Now, if it is, e.g., $w_1$ and $w_3$, we have a contradiction because $w_1 + w_3 \geq 1$ but $(1, 0, 1, 0)$ is rejected; the other cases are analogous.

This looks to me like a very natural problem, so my main question is to know under which name this has been studied. Asking for a "characterization" is vague, of course; my question is to know whether the class of functions that can be represented in this way has a name, what is known about the complexity of testing whether an input function belongs to it (given as a formula, or as a circuit), etc.

Of course one can think of many variations on this theme. For instance, on real exams, questions are not independent, but there is a DAG on questions indicating the dependence, and candidates can only answer a question if all prerequisites have been answered. The condition on the monotone functions could then be restricted to valuations in $\{0, 1\}^n$ that satisfy the dependencies, and the question would be to determine whether an input function can be thus captured given an input DAG on the variables. One could also think of variants where the scores are $k$-tuples for fixed $k$ (summed pointwise, and compared pointwise to a threshold vector), which can capture more functions than $k = 1$. Alternatively you could want to capture more expressive functions which are not Boolean but go to a totally ordered domain, with different thresholds that should indicate your position in the domain. Last, I'm not sure about what would happen if you allowed negative scores (so you could drop the monotone restriction about the functions).

(Note: What made me wonder about this is the Google Code Jam selection round, where candidates are selected if they reach a certain score threshold, and the scores of problems are presumably carefully designed to reflect what sets of problems are deemed sufficient to get selected. Code Jam has a dependency structure on the questions, with some "large input" questions that cannot be solved unless you have solved the "small input" one first.)

$\endgroup$
  • $\begingroup$ These are known as threshold functions (though this term is sometimes defined more restrictively). I don't know if there is an essentially different characterization. An obvious necessary condition is that $f^{-1}(1)$ and $f^{-1}(0)$ are convex (that is, the convex hull of $f^{-1}(1)$ intersected with $\{0,1\}^n$ is included in $f^{-1}(1)$, and similarly for 0). $\endgroup$ – Emil Jeřábek May 13 '15 at 11:15
  • $\begingroup$ Actually, now that I think about it: a Boolean function $f$ is a threshold function iff the convex hulls of $f^{-1}(1)$ and $f^{-1}(0)$ are disjoint. $\endgroup$ – Emil Jeřábek May 13 '15 at 11:21
  • 2
    $\begingroup$ Actually, these are more precisely the positive threshold functions. $\endgroup$ – Kristoffer Arnsfelt Hansen May 13 '15 at 15:32
  • $\begingroup$ @KristofferArnsfeltHansen: Exactly, thanks! In fact this is mentioned in Boolean Functions: Theory, Algorithms, and Applications. Theorem 9.16 says that given a positive DNF we can, in PTIME, test whether it is a threshold function, and if yes construct a vector $\mathbf{w}$ (which will then be positive, I think, by Theorem 9.6). Is anything known about the variants I suggested, especially the one with a DAG on the variables? If not, you are welcome to make an answer that says so (and subsumes your comment), and I will accept it. :) $\endgroup$ – a3nm May 21 '15 at 17:51
2
$\begingroup$

It was mentioned in the comments that these are the positive threshold functions.

As for other characterizations, I found the following to be interesting. Suppose we have a positive threshold function with decreasing weights $w_1\ge w_2\ge\dots w_n$: $$f(v_1,\dots,v_n)=1 \iff \sum_i w_iv_i\ge 1.$$ Then in particular the set of inputs $(v_1,\dots,v_n)$ for which $f(\vec v)=1$ is an order ideal of the binary majorization lattice with $2^n$ points, which is studied in

Donald Knuth, "The Art of Computer Programming", Exercise 109 of Section 7.1.1.

To put it informally, $f$ is the kind of function where making earlier bits 1 makes $f$ more likely to be 1: so e.g. $f(0,1,1)\le f(1,0,1)\le f(1,1,0)$. That is, "some bits matter more", and to remove redundant isomorphic cases we assume earlier bits matter more.

However, not all such functions are positive threshold functions! That is, just because you've ordered the exam questions from most important to least doesn't mean your pass/fail rule is based on just adding up some scores.

Indeed, the number of positive threshold functions (with decreasing weights) on $n$ variables is given by the sequence $$2,3,5,10,27,119,\mathbf{1113},\dots$$ (oeis.org sequence A000617) whereas the number of such order ideals is $$2,3,5,10,27,119,\mathbf{1173},\dots$$ (oeis.org sequence A132183)

$\endgroup$
  • $\begingroup$ Thanks! Just thought I'd point out that the other kind of Boolean functions mentioned in your answer, the ones with a total order on the influence of variables, are called "regular" Boolean functions. This is mentioned in sequence A132183, and such functions are studied in Chapter 8 of Boolean Functions: Theory, Algorithms, and Applications $\endgroup$ – a3nm Sep 2 '18 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.