Complexity index

Besides complexity intended as a difficulty to compute a function (see computational complexity), in modern computer science and in statistics another complexity index of a function stands for denoting its information content, in turn affecting the difficulty of learning the function from examples. Complexity indices in this sense characterize the entire class of functions to which the one we are interested in belongs. Focusing on Boolean functions, the detail of a class

To identify this index we must first define a sentry function of

 . Let us focus for a moment on a single function c, call it a concept defined on a set 

 . We may dually define these points in terms of sentinelling a given concept c from being fully enclosed (invaded) by another concept within the class. Therefore, we call these points either sentinels or sentry points; they are assigned by the sentry function 

the sentry points are external to the concept c to be sentineled and internal to at least one other including it,

each concept

 , or outside 

they constitute a minimal set with these properties.

The technical definition coming from (Apolloni 2006) is rooted in the inclusion of an augmented concept