Paper Info
Title
Inner-core and outer-core functions of partially defined Boolean functions
Abstract
Given 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.
Year
DOI
Venue
1999
10.1016/S0166-218X(99)00101-8
Discrete Applied Mathematics
Keywords
Field
DocType
outer-core function,boolean function,inner core
Boolean network,Boolean function,Karp–Lipton theorem,Discrete mathematics,Inner core,Combinatorics,Polynomial,Parity function,Time complexity,Boolean expression,Mathematics
Journal
Volume
Issue
ISSN
96-97
1
Discrete Applied Mathematics
Citations 
PageRank 
References 
7
0.67
7
Authors
2
Name
Order
Citations
PageRank
Kazuhisa Makino11088102.74
Toshihide Ibaraki22593385.64