Positive and Horn decomposability of partially defined Boolean functions (Q1356507)

Let \(T\) be a set of positive examples, \(F\) a set of negative examples, i.e. \(T,F\subset\{0,1\}^n\), \(T\cap F=\emptyset\), and let \((T,F)\) be the partially defined Boolean function (pdBf), defined by \[ (T,F)(\nu)=\begin{cases} 1\text{ if }\nu\in T\\ 0\text{ if }\nu\in F\end{cases} \] Given a pdBf \((T,F)\) and a family of subsets \(S_i\subseteq\{1,2,\dots,n\}\), \(i=0,\dots,k\), the decomposability problem is to decide the existence of Boolean functions \(h_1,\dots,h_k\), \(g\) such that the function \(f(\nu)=g(\nu[S_0],h_1(\nu[S_1]),h_2(\nu[S_2]),\dots,h_k(\nu[S_k]))\) is an extension of the pdBf \((T,F)\), where \(\nu[S]\) denotes the projection of the vector \(\nu\) on the subset \(S\) of indices. Let \(P\), \(H\) denote classes of positive and Horn functions and let, e.g., \(P(S_0,P(S_1),\dots,P(S_k))\) be a decomposition \(g(\nu[S_0],h_1(\nu[S_1]),h_2(\nu[S_2]),\dots,h_k(\nu[S_k]))\) where all functions \(g\), \(h_i\) are positive. Several results on the complexity of finding decompositions have been obtained, e.g., it is shown that for schemes \(P(S_0,P(S_1),P(S_2),P(S_3))\), \(P(S_0,P(S_1),H(S_2))\) the decomposability problem is NP-complete, but \(P(P(S_1),H(S_2))\) and \(H(P(S_1),P(S_2))\) both can be solved in polynomial time.