Rivest-Vuillemin conjecture is true for monotone Boolean functions with twelve variables (Q1613515)

A decision tree of a Boolean function \(f\) is a rooted binary tree, whose nonleaf vertices are labeled by its variables, and leaves are labeled by \(0\) and \(1\). Edges are labeled such that edges from a nonleaf vertex to its successors are labeled by \(0\) and \(1\), respectively, and every variable appears at most once in an path from the root to a leaf. Given an assignment to variables of a Boolean function \(f(x_1, x_2,\dots, x_n)\), the function \(f\) can be computed by its decision tree. A Boolean function \(f(x_1, x_2,\dots, x_n)\) is called elusive if every decision tree computing \(f\) must examine \(n\) variables in the worst case. It ist a long-standing conjecture that every nontrivial monotone weakly symmetric Boolean function is elusive. In this paper, every Boolean function with twelve variables is proved to be elusive.