Inner-core and outer-core functions of partially defined Boolean functions

AbstractGiven a class of functions C, we introduce the k-inner-core and k-outer-core functions of a partially defined Boolean function (T,F), in order to identify the set of vectors which are immune up to k classification errors in T∪F, where T denotes a set of true vectors (or positive examples) and F denotes a set of false vectors (or negative examples). We restrict C to classes C+ and C⊨ of positive and regular functions, respectively, and investigate various problems associated with inner-core and outer-core functions. In particular, we show that there is no polynomial total time algorithm for computing the k-inner-core function for class C+ and general k, unless P=NP; but there is an input polynomial time algorithm if k is fixed. The situation for the outer-core function is different. It is shown that, for class C+ and a fixed k, there is a polynomial total time algorithm for computing the k-outer-core function if and only if there is a polynomial total time algorithm for dualizing a positive Boolean function (the complexity of this problem is not known yet). For class C⊨, there are incrementally polynomial time algorithms for computing both the k-inner-core and k-outer-core functions