Índice de complejidad

En la informática y la estadística modernas , el índice de complejidad de una función denota el nivel de contenido informativo, que a su vez afecta la dificultad de aprender la función a partir de ejemplos . Esto es diferente de la complejidad computacional , que es la dificultad para calcular una función. Los índices de complejidad caracterizan a toda la clase de funciones a las que pertenece la que nos interesa. Centrándose en las funciones booleanas , el detalle de una clase de funciones booleanas c denota esencialmente qué tan profundamente se articula la clase.${\ Displaystyle {\ mathsf {C}}}$

Para identificar este índice, primero debemos definir una función centinela de . Centrémonos por un momento en una única función c , llamémosla concepto definido en un conjunto de elementos que podemos figurar como puntos en un espacio euclidiano . En este marco, la función anterior asocia ac un conjunto de puntos que, al estar definidos como externos al concepto, impiden que se expanda a otra función de . Podemos definir doblemente estos puntos en términos de evitar que un concepto c dado esté completamente encerrado (invadido) por otro concepto dentro de la clase. Por lo tanto, llamamos a estos puntos centinelas o puntos de centinela.${\ Displaystyle {\ mathsf {C}}}$${\ Displaystyle {\ mathcal {X}}}$${\ Displaystyle {\ mathsf {C}}}$; son asignados por la función de centinela a cada concepto de de tal manera que:${\ displaystyle {\ boldsymbol {S}}}$${\ Displaystyle {\ mathsf {C}}}$

La definición técnica procedente de ( Apolloni 2006 ) se basa en la inclusión de un concepto aumentado compuesto por c más sus centinelas por otro de la misma clase.error de harv: sin destino: CITEREFApolloni2006 ( ayuda )${\displaystyle c^{+}}$${\displaystyle \left(c'\right)^{+}}$

Para una clase de concepto en un espacio , una función centinela es una función total que satisface las siguientes condiciones:${\displaystyle {\mathsf {C}}}$${\displaystyle {\mathfrak {X}}}$ ${\displaystyle {\boldsymbol {S}}:{\mathsf {C}}\cup \{\emptyset ,{\mathfrak {X}}\}\mapsto 2^{\mathfrak {X}}}$

${\displaystyle {\boldsymbol {S}}(c)}$es la frontera de c on .${\displaystyle {\boldsymbol {S}}}$

Una perspectiva esquemática de la funcionalidad centinela exterior

Dos puntos fuera de c (círculo grueso) son suficientes para evitar que un círculo más grande que no los contenga lo incluya${\displaystyle x_{1},x_{2}}$

La clase de segmentos en y dos puntos necesarios para centrar sus conceptos.${\displaystyle \mathbb {R} }$