Том 7, серия 1, номер 1, 2000 г., Стр. 79-93

УДК 519.95
Е. А. Окольнишникова
О двух операциях над булевыми функциями

Аннотация:
Показано, что операции геометрического проектирования и монотонного расширения булевых функций могут приводить к усложнению реализаций булевых функций в ряде классов схем, а также в классе ветвящихся $k$-программ. Установлено, что если существует «большой разрыв» между сложностями реализации некоторой функции в классе недетерминированных и в классе детерминированных ветвящихся программ (ветвящихся $k$-программ), то можно построить пример такой функции, что существует «большой» разрыв между сложностью реализации этой функции и ее проекцией в классе детерминированных ветвящихся программ (ветвящихся $k$-программ).
Ил. 2, библиогр. 12.

Окольнишникова Е. А. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 20 декабря 1999 г.