Cтраница 4
В разделе 3 методы работы [13] применяются для получения нашей новой нижней оценки. Определяется мера сложности, которая учитывает только элементы Л, причем в схемах допускается свободное вхождение некоторых функций. Для получения нижних оценок для монотонной сложности достаточно нахождения нижних оценок для указанной новой меры сложности. Поскольку допускается свободное вхождение некоторых функций и элементов V, становится возможным преобразовывать минимальную монотонную схему, реализующую систему млм ез увеличения ее сложности в смысле рассматриваемой новой меры. В результате этих преобразований получается схема, реализующая / лш о строении которой многое известно. [46]
Вершины соединим по следующему правилу. Если к / - му входу ( с весом Wj) некоторого элемента присоединен выход другого элемента ( или вход схемы), соединим соответствующие вершины Wj параллельными ребрами, направленными к первой вершине, и припишем им знак Wj, то по полученному графу схема с точностью до изоморфизма восстанавливается однозначно. Для получения нижней оценки нам необходимо оценить сверху количество таких графов. [47]
В настоящее время накоплен достаточно большой материал по оценкам сложности различных классов объектов при тех или иных формальных определениях понятия сложность. Это и информационная сложность ряда классов непрерывных экстремальных задач, и сложность синтеза основных классов так называемых управляющих систем ( схемы, формулы, алгоритмы), и алгоритмическая ( вычислительная) сложность дискретных объектов. Однако по-прежнему получение нижних оценок сложности и построение верхних оценок, близких к нижним, для новых неизученных классов задач остается весьма тонкой и трудоемкой аа-дачей. [48]
Из [3-5] известно, что сложность схем для булевых функций тесно связана с величиной произведения времени работы и объема программы машин Тьюринга, вычисляющих их. Поэтому представляет интерес получение нижних оценок сложности схем для. Обычно трудно вычислить точное значение сложности схемы для булевой функции. [49]