6
\$\begingroup\$

Let \$\mathbb{B} = \mathbb{Z}_2 = \{0, 1\}\$ be the set of booleans. A symmetric boolean function in \$n\$ arguments is a function \$f_S : \mathbb{B}^n \to \mathbb{B}\$ that checks if the number of its true arguments is in \$S\$, i. e. a function \$f_S\$ such that

$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = \left(\sum_{1 \le i \le n}\alpha_{i}\right) \in S$$

or equivalently

$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = |\{ i : \alpha_i \}| \in S. $$

These functions are called symmetric boolean function because they are all the boolean function that do not depend on argument order.

The set of boolean numbers forms a field, conventionally denoted \$GF(2)\$, where multiplication is logical and (\$\wedge\$) and addition is exclusive or (\$\oplus\$). This field has the properties that \$-\alpha = \alpha\$, \$\alpha / \beta = \alpha \wedge \beta\$ (for all \$\beta \neq 0\$), \$\alpha \oplus \alpha = 0\$ and \$\alpha \wedge \alpha = \alpha\$ for all \$\alpha\$ in addition to the field properties. For convenience, I am going to write \$\oplus\$ as \$+\$ and leave out \$\wedge\$ in the next paragraphs. For example, I will write \$\alpha \oplus \beta \oplus \alpha \wedge \beta\$ as \$\alpha + \beta + \alpha\beta\$.

Every boolean function can be expressed as a polynomial over the field of boolean numbers. Such a polynomial is called a Zhegalkin polynomial, the representation is canonical, i. e. there is exactly one polynomial that represents a given boolean function. Here are some examples for boolean functions and their corresponding Zhegalkin polynomials:

  • \$\alpha \vee \beta = \alpha + \beta + \alpha\beta\$
  • \$\alpha \wedge \neg\beta = \alpha + \alpha\beta\$
  • \$(\alpha \to \beta) \oplus \gamma = 1 + \alpha + \gamma + \alpha\beta\$
  • \$\neg(\alpha \wedge \beta) \vee \gamma = 1 + \alpha\beta + \alpha\beta\gamma\$
  • \$f_{\{1, 4\}}(\alpha, \beta, \gamma, \delta) = \alpha + \beta + \gamma + \delta + \alpha\beta\gamma + \alpha\beta\delta + \alpha\gamma\delta + \beta\gamma\delta + \alpha\beta\gamma\delta\$
    where the triple terms \$(\alpha\beta\gamma + \alpha\beta\delta + \alpha\gamma\delta + \beta\gamma\delta)\$ are required because otherwise we would have \$f(1,1,1,0) = 1\$, and \$3 \not\in \{1, 4\}\$.

One observation we can make is that due to symmetry, the Zhegalkin polynomial for a symmetric boolean function always has the form

$$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n) = \sum_{i \in T_{S,n}}t_{n,i}$$

where \$\sum\$ denotes summation with exclusive or and \$t_{n, i}\$ is the sum of all product terms that use \$i\$ out of the \$n\$ arguments to \$f_S\$ and \$T_{S,n} \subseteq \{0, 1, \ldots, n\}\$ is a set describing those \$t_{n, i}\$ we need to construct \$f_S(\alpha_1, \alpha_2, \ldots, \alpha_n)\$. Here are some examples for \$t_{n, i}\$ so you can get an idea what they look like:

  • \$t_{4, 1} = \alpha + \beta + \gamma + \delta\$
  • \$t_{3, 2} = \alpha\beta + \alpha\gamma + \beta\gamma\$
  • \$t_{4, 4} = \alpha\beta\gamma\delta\$
  • for all \$n\$: \$t_{n, 0} = 1\$

We can thus describe an \$f_S\$ in \$n\$ arguments completely by \$n\$ and \$T_{S, n}\$. Here are some test cases:

  • \$T_{\{1, 4\}, 4} = \{1, 3, 4\}\$
  • \$T_{\{2, 3, 4\}, 4} = \{2, 4\}\$
  • \$T_{\{2\}, 4} = \{2, 3\}\$
  • \$T_{\{1, 2\}, 2} = \{1, 2\}\$ (logical or)
  • \$T_{\{2, 3\}, 3} = \{2\}\$ (median function)

The task in this challenge is to compute \$T_{S, n}\$ given \$S\$ and \$n\$. You can choose an appropriate input and output format as you like. This challenge is code-golf, the shortest solution in octets wins. As a special constraint, your solution must run in polynomial time \$O(n^k)\$ where \$n\$ is the \$n\$ from the input.

\$\endgroup\$
  • \$\begingroup\$ I think T_{2, 3}, 3 should be {2}. \$\endgroup\$ – alephalpha Nov 5 '15 at 3:37
  • \$\begingroup\$ @alephalpha Of course. \$\endgroup\$ – FUZxxl Nov 5 '15 at 9:21
  • \$\begingroup\$ @alephalpha: what about if x1=x2=x3=True? Then f{2}(x1,x2,x3) should be False, but sum(t_n,i), for i in {T_{2,3]}} = sum(t_n,i) for i in {2} = t_3,2 = x1 * x2 + x1 * x3 + x2 * x3 = T * T + T * T + T * T = T. Or am i misunderstanding the notation here? \$\endgroup\$ – njnnja Nov 5 '15 at 18:50
  • \$\begingroup\$ @njnnja T_{2,3},3 describes f{2,3}(x1,x2,x3), not f{2}(x1,x2,x3). I hope this clears up your misunderstanding. \$\endgroup\$ – FUZxxl Nov 5 '15 at 18:54
  • \$\begingroup\$ @PeterTaylor No. If α = β = γ = 1 and δ = 0 you would get 1 + 1 + 1 + 0 + 1∧1∧1∧0 = 1 which is wrong for f_{1, 4} as 3 is not in {1, 4}. I admit the description is a bit ambiguous: In the first paragraph (and only there), ∑ denotes a sum over integers, not over booleans. \$\endgroup\$ – FUZxxl Nov 5 '15 at 22:47
7
\$\begingroup\$

Dyalog APL, 15 bytes

{2|⍺⌹⍉∘.!⍨0,⍳⍵}

Matrix division, basically. Takes input like 0 0 1 1 1 {2|⍺⌹⍉∘.!⍨0,⍳⍵} 4 for T4({2,3,4}).

{              }        Dyadic function:
              ⍵         Right argument          4
             ⍳          Index vector            1 2 3 4
           0,           Append 0                0 1 2 3 4
      ∘.                Outer product           ——————————
          ⍨             |With itself              1 0 0 0 
        !               |By binomial coeff.       2 1 0 0
     ⍉                  Matrix transpose          3 3 1 0
                        Result at this step: ->   4 6 4 1
   ⍺                    Left argument
    ⌹                   Matrix division (A⌹B is A^-1 B, not A B^-1)
                        (implicitly converts ⍺ to column vector)
 2|                     Modulo 2

Since the transposed matrix of binomial coefficients is lower triangular with determinant 1, its inverse will only contain integers. So to matrix-divide over F2 we can just matrix-divide over the reals, then mod by 2.

Matrix division is an O(n^3) operation, and calculating each of the O(N^2) binomial coefficients is well below O(n^3), so this runs in O(N^5).

Try it on TryAPL.

\$\endgroup\$
  • \$\begingroup\$ Neato! I expected nothing less than this from APL. \$\endgroup\$ – FUZxxl Nov 6 '15 at 0:01
1
\$\begingroup\$

CJam (25 24 bytes)

{_,{1$_,,2$~f&:!.*:^t}/}

This is an anonymous function which takes an array of 0 or 1 which serves as an indicator function for \$S\$ and returns an array of 0 or 1 which serves as an indicator function for \$T\$. E.g. to find \$T_{\{1, 4\}, 4}\$ you pass [0 1 0 0 1] and it returns [0 1 0 1 1].

Online demo

Explanation

Recall that \$t_{n,i}\$ is the sum of all product terms that use \$i\$ out of the \$n\$ arguments to \$f_S\$. Suppose that \$s\$ of the \$n\$ arguments are true. Then we have three cases for \$t_{n,i}(\alpha_0, \ldots, \alpha_{n-1})\$:

  • \$i > s\$ : none of the terms is true, so \$t_{n, i}(\alpha_0, \ldots, \alpha_{n-1}) = 0\$
  • \$i = s\$ : exactly one of the terms is true, so \$t_{n, i}(\alpha_0, \ldots, \alpha_{n-1}) = 1\$
  • \$i < s\$ : there are \$\binom{s}{i}\$ terms which are true, so \$t_{n, i}(\alpha_0, \ldots, \alpha_{n-1}) = \binom{s}{i} \bmod 2\$

If we let \$\sigma\$ be the indicator function for \$S\$ and \$\tau\$ be the indicator function for \$T_{S, n})\$, we therefore get the matrix identity

$$\begin{pmatrix}1 & 0 & 0 & \ldots & 0 \\ \binom{1}{0} & 1 & 0 & \ldots & 0 \\ \binom{2}{0} & \binom{2}{1} & 1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & 0 \\ \binom{n}{0} & \binom{n}{1} & \binom{n}{2} & \ldots & 1 \end{pmatrix} \begin{pmatrix}\tau(0) \\ \tau(1) \\ \tau(2) \\ \vdots \\ \tau(n) \end{pmatrix} = \begin{pmatrix}\sigma(0) \\ \sigma(1) \\ \sigma(2) \\ \vdots \\ \sigma(n) \end{pmatrix} $$

which is dead easy to solve because the coefficient matrix is already in row-reduced echelon form.

Note that this is quite a well-known matrix, because it's the binomial coefficients modulo 2, which famously forms a Sierpiński triangle. I calculate them using Lucas' theorem and bit-twiddling as 2$~f&:!

\$\endgroup\$
  • \$\begingroup\$ Notice that all three cases can be reduced to the third. \$\endgroup\$ – FUZxxl Nov 7 '15 at 0:55
  • \$\begingroup\$ Yes, and I'm implicitly relying on that when calculating the matrix, but from a didactic point of view I think it's preferable to split them up. \$\endgroup\$ – Peter Taylor Nov 7 '15 at 7:42
0
\$\begingroup\$

R, 115 bytes

function(S,n)which(abs(solve(sapply(1:n,function(k)(sapply(1:n,function(j)choose(j,k)%%2))),is.element(1:n,S)))==1)

The key is realizing that the sum of t's that evaluate to a T value is just the choose function. A slightly ungolfed version that doesn't calculate in polynomial time is below, but illustrates the derivation of the t's a little better (just run the middle line).

function(S,n)which(abs(solve(
sapply(1:n,function(k)(sapply(1:n,function(j)sum(apply(combn(c(rep(T,j),rep(F,max(0,k-j))),k),2,all))%%2))),
is.element(1:n,S)))==1)
\$\endgroup\$
  • \$\begingroup\$ Are you sure choose(j,k) computes in polynomial time? I doubt that since the binomials grow exponentially. \$\endgroup\$ – FUZxxl Nov 5 '15 at 22:49
  • \$\begingroup\$ The binomials grow exponentially in n, but the number of digits goes linearly. You mean polynomial time in n, not polynomial time in log n (size of input), right? \$\endgroup\$ – lirtosiast Nov 5 '15 at 23:04
  • 1
    \$\begingroup\$ The golfed version does. The ungolfed version expands all the necessary combinations and is O(n!) (or worse, just guessing). But the golfed function uses the choose function, which is a closed formula =n!/(n-k)!k! which only requires 2 extra calculations when incrementing n by 1, and is therefore O(n^1). Note that we are looking at the binomial expansion in the ungolfed version; but in the golfed version we just multiply n integers together. I.e. g(n)=n! is not O(n!) complexity \$\endgroup\$ – njnnja Nov 5 '15 at 23:10
  • \$\begingroup\$ @ThomasKwa Yeah, polynomial time in n, not in log n. \$\endgroup\$ – FUZxxl Nov 5 '15 at 23:57

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.