Индекс сложности

В современной информатике и статистике индекс сложности функции обозначает уровень информативности, что в свою очередь влияет на сложность изучения функции на примерах . Это отличается от вычислительной сложности , которая представляет собой сложность вычисления функции. Показатели сложности характеризуют весь класс функций, к которому принадлежит интересующая нас функция. Сосредоточив внимание на булевых функциях , детализация класса булевых функций c по существу указывает, насколько глубоко артикулирован класс. ${\ Displaystyle {\ mathsf {С}}}$

Чтобы идентифицировать этот индекс, мы должны сначала определить часовую функцию . Давайте на мгновение сосредоточимся на одной функции с , назовем ее концепцией , определенной на множестве элементов, которые мы можем изобразить как точки в евклидовом пространстве . В этой структуре вышеупомянутая функция связывает с набор точек, которые, поскольку определены как внешние по отношению к понятию, предотвращают его расширение в другую функцию от . Мы можем двояко определить эти точки в терминах охраны данного понятия с от полного включения (вторжения) другого понятия в пределах класса. Поэтому мы называем эти точки либо дозорными , либо дозорными . ${\ Displaystyle {\ mathsf {С}}}$ ${\ displaystyle {\ mathcal {X}}}$ ${\ Displaystyle {\ mathsf {С}}}$ ; они назначаются часовой функцией каждому понятию таким образом, что: ${\ displaystyle {\boldsymbol {S}}}$ ${\ Displaystyle {\ mathsf {С}}}$

Техническое определение, взятое из ( Аполлони, 2006 ) , основано на включении расширенного понятия , состоящего из с плюс его контрольные точки, другим в том же классе. $c^{+}$ $\left(c'\right)^{+}$

Для класса понятий в пространстве сторожевая функция является тотальной функцией, удовлетворяющей следующим условиям: ${\mathsf {C}}$ ${\mathfrak {X}}$ ${\boldsymbol {S}}:{\mathsf {C}}\cup \{\emptyset ,{\mathfrak {X}}\}\mapsto 2^{\mathfrak {X}}$

${\boldsymbol {S}}(c)$ является границей c на . _ ${\boldsymbol {S}}$

Схематический вид внешней сторожевой функциональности

Две точки за пределами c (толстый круг) достаточны, чтобы окружность большего размера, не содержащая их, не включала ее.

x_{1},x_{2}

Класс сегментов и две точки, необходимые для обозначения его понятий .

\mathbb {R}