UDK 51 Математика
GRNTI 27.35 Математические модели естественных наук и технических наук. Уравнения математической физики
OKSO 01.04.04 Прикладная математика
BBK 221 Математика
TBK 6025 Теория систем
BISAC MAT034000 Mathematical Analysis
Effective algorithms are provided for checking presence of joint action of k factors in a given outcome which depends on n factors (k < n) and for calculation of degrees of that joint action for any k. It is demonstrated that asymptotic time complexity of the proposed algorithms does not exceed square of the input data size representing the given outcome
Boolean functions, Boolean cube, effective algorithm, computational complexity, binary sufficient cause theory, outcome.
Введение. Булева модель теории достаточных причин, предложенная в работах [1-8], позволяет рассматривать эту эпидемиологическую концепцию как приложения общей теории конечных булевых алгебр и булевых функций [9, 10]. При этом помимо прояснения и формализации основных понятий этой концепции возникает необходимость разработки эффективных алгоритмов [11, 12], вычисляющих различные величины обсуждаемой теории. При этом важно не только предложить эти алгоритмы, но и оценить их вычислительную сложность [11, 12], поскольку размер входных данных для этих алгоритмов в булевом формализме теории достаточных причин достаточно высок.
Ниже мы рассмотрим оценки асимптотической временнóй вычислительной сложности проверки наличия совместного действия факторов в отклике и нахождения степени этого совместного действия [5, 6, 8], применяемых в задаче классификации совместного действия факторов в бинарной теории достаточных причин.
Предварительно заметим, что речь будет идти только об асимптотической сложности, которая обычно используется в теории сложности алгоритмов [11, 12], что связано с размером входных данных обсуждаемой задачи, зависящим от числа факторов экспоненциально. Действительно, булев куб 
имеет 2n вершин, а любой двухуровневый отклик f от n (булевых) переменных полностью определятся своим носителем 
, причем
[7]. Так как вершина булева куба определяется бинарным вектором длины n, то размер входных данных, задающих отклик f, в худшем случае равен N = n·2n. Следовательно, уже при сравнительно небольшом числе факторов объем исходных данных становится слишком большим, что делает необходимым построение эффективных алгоритмов вычисления различных конструкций этой теории, причем один из параметров оценки алгоритма как эффективного является минимизация его вычислительной сложности. Кроме того, следует отметить, что имеющиеся модели теории достаточных причин как в формальном [1-8], так и в полуформальном изложении [14-16] допускают произвольное число факторов. Поэтому уже с точки зрения полноты этой теории рассмотрение всех вопросов, возникающих в контексте того или иного формализма, совершенно естественно и необходимо.
Одно из важных общих понятий булевой модели теории достаточных причин – понятие совместного действия n факторов в отклике, зависящем от всех этих n факторов, введено в работах [5,7]. В работе [7] также был приведён эффективный алгоритм проверки по данному отклику наличия в нём совместного действия всех его факторов, а также приведена оценка сверху временнóй сложности этого алгоритма величиной 
.
Основные результаты
В работах [6, 8] было предложено понятие взаимодействия k 
факторов в отклике, зависящем от n факторов, которое обобщает понятия взаимодействия n факторов в отклике, зависящем от n факторов. С помощью критерия совместного действия k факторов, предложенного в [6], можно доказать аналогичную оценку временнóй сложности эффективного алгоритма проверки наличия этого действия в данном отклике. Формулировка этого критерия (см. Теорему 1 ниже) использует представления отклика f в виде неориентированного графа 
, который является подграфом булева куба с вершинами из носителя Cf.
Теорема 1 [6]. В отклике f , зависящем от n факторов, имеется взаимодействие k факторов тогда и только тогда, когда минимальная степень вершин в графе 
не превосходит n – k.
Теорема 2. Для любого k 
существует эффективный алгоритм, проверяющий наличие совместного действия k факторов в отклике, зависящем от n факторов, причем временнáя сложность этого алгоритма имеет порядок не более чем 
.
Доказательство. Каждый автоморфизм 
булева куба может быть продолжен на свободную булеву алгебру всех булевых функций от переменных 
. При этом булевой функции f соответствует булева функция 
чей носитель 
равен образу 
носителя 
функции f. Пусть 
- произвольная вершина графа 
. Рассмотрим автоморфизм 
булева куба , определяемый равенством 
где 
сложение по модулю 2. Любой автоморфизм булева куба является изометрией этого куба как метрического пространства с метрикой-расстоянием Хэмминга. Поэтому степень вершины γ в графе равна степени вершины 0 в графе 
, вершинно-порожденном множеством 
. Степень вершины 0 в графе равна числу вершин единичного веса Хэмминга в множестве 
Получение списка таких вершин и подсчёт их числа имеют сложность не более чем 
. Следовательно, вычисление степени любой вершины в графе имеет временнýю сложность не более чем 
, а вычисление минимальной степени вершин в этом графе – не более чем 
.
Таким образом, оценка 
экспоненциальна по числу факторов n, но менее чем квадратична по наибольшему размеру входных данных 
Для исследования совместного действия факторов в данном отклике в работах [5,7] было введено понятие степени 
совместного действия n факторов в отклике f. В работе [7] также предложен эффективный алгоритм нахождения и показано, что верхняя оценка сложности этого алгоритма равна 
.
В работе [6] было введено обобщение этого понятия – степень 
совместного действия k факторов в отклике f, зависящем от n факторов, а в работе [8] рассмотрена зависимость степени от k. Следующее утверждение даёт оценку сложности вычисления набора 
степеней совместного действия для данного отклика f.
Теорема 3. Существует эффективный алгоритм вычисления набора 
степеней совместного действия данного отклика f, причем сложность этого алгоритма оценивается сверху величиной порядка 
где N, как и раньше, максимальный размер входных данных, 
.
Доказательство. Рассмотрим булев куб как решёточно-упорядоченное множество 
относительно покомпонентного сравнения ‘≤’ бинарных векторов [10], которое можно представить ориентированным графом R. В графе R для каждого 
выделены списки Uk лексикографически упорядоченных вершин веса k. На формирование графа R потребуется времени (элементарных шагов вычислительных операций) не более чем 
. Далее для каждого набора 
производим следующие шаги:
- формируем список лексикографически упорядоченных вершин множества Cg, где
из списка вершин множества Cf. - полученный список распределяем по спискам Vk,
, вершин веса k, для которых сохраняется лексикографическое упорядочение; - при помощи списков Vk из графа R получаем помеченный ориентированный граф Rg, в котором каждая вершина
из списка Uk помечается числом 
если 
и 
в противном случае. Таким образом, граф Rg представляет частично упорядоченное множество 
.
Шаги (1)-(3) в целом займут времени не более чем .
- для каждой вершины графа
из списка Uk вычисляем метку 
с помощью метки 
и меток 
для k вершин 
из списка Uk-1, покрываемых вершиной 
в 
(считая, что m(0)=0); - для каждого
находим mk – максимальное значение среди всех вершин графа из списка Uk.
На этапы (4)-(5) потребуется время не более чем 
Шаги (1)-(5) повторяются для каждого набора и поэтому в целом выполняемые действия потребуют времени не более чем 
, что не превосходит 
На последнем шаге для каждого k находим максимальное значение среди всех тех mk, которые вычисляются на этапе (5) для всех вершин 
Можно доказать, что полученное значение равно степени .
Таким образом, в целом, описанный динамический алгоритм имеет временнýю сложность не более чем 
1. Panov V. G., Nagrebeckaya Yu. V. Algebraicheskaya traktovka dvuhfaktornoy teorii dostatochnyh prichin // Trudy SPIIRAN. 2013. T. 3(26). S. 277–296.
2. Panov V. G., Nagrebeckaya Yu. V. Algebraicheskaya klassifikaciya sovmestnogo deystviya n binarnyh faktorov // Materialy IX mezhdunar. konf. «Sistemnyy analiz v medicine». Blagoveschensk. 2015. S. 31–34.
3. Panov V.G. and Nagrebetskaya J.V. Boolean algebras and classification of interactions in sufficient-component cause model // Int. J. Pure Appl. Math. 2015. V. 98(2). P. 239–259.
4. VanderWeele T.J., Robins J.M. A theory of sufficient cause interactions // COBRA Preprint Series. 2006. Paper 13.
5. Nagrebeckaya Yu.V., Panov V.G. Stepen' vzaimodeystviya binarnyh faktorov v teorii dostatochnyh prichin // Materialy XIII mezhdunar. konf. "Sistemnyy analiz v medicine". Blagoveschensk, 2019. C. 31–34.
6. Nagrebeckaya Yu. V., Panov V. G. Obobschenie ponyatiya vzaimodeystviya n faktorov v teorii dostatochnyh prichin i ego svoystva // Materialy XIII mezhdunar. konf. "Sistemnyy analiz v medicine". Blagoveschensk, 2019. C. 35–38.
7. Nagrebetskaya J.V., Panov V.G. Joint action of binary factors in the sufficient causes theory and its classification // Int. J Innov. Tech.&Exploring Eng. V.9(1), 2019. P. 2146–2153.
8. Yablonskiy S. V. Vvedenie v diskretnuyu matematiku. M.: Nauka, 1986.
9. Lidl R., Pil'c G. Prikladnaya abstraktnaya algebra. Ekaterinburg: Izd-vo Ural'skogo un-ta, 1996.
10. Geri M., Dzhonson D. Vychislitel'nye mashiny i trudnoreshaemye zadachi. M.: Mir, 1982.
11. Aho. A., Hopkroft Dzh., Ul'man Dzh. Postroenie i analiz vychislitel'nyh algoritmov. M.: Mir, 1979.
12. Rothman K. Causes // Am. J. Epidemiology. 1976. V. 104(6). P. 587–592.
13. Miettinen O. S. Causal and preventive interdependence: Elementary principles // Scand. J. Work. Environ. Health. 1982. V. 8. P. 159–168.
14. VanderWeele T. J., Robins J. M. The identification of synergism in the sufficient-component-cause framework // Epidemiology. 2007. V. 18(3). P. 329–339.
15. VanderWeele T. J., Richardson T. S. General theory for interactions in sufficient cause models with dichotomous exposures // Ann. Statistics. 2012. V. 40. P. 2128–2161.
