Том 20, номер 3, 2013 г., Стр. 84-100

УДК 519.71
Фёдорова В. С.
О сложности проблемы выполнимости системы функциональных булевых уравнений

Аннотация:
Рассматриваются функциональные булевы уравнения и проблема распознавания выполнимости для них, которая состоит в следующем: существуют ли булевы функции, удовлетворяющие данному функциональному уравнению. Устанавливаются верхняя и нижняя оценки сложности проблемы выполнимости системы функциональных булевых уравнений, тем самым обосновывается невозможность её решения методом, который существенно проще непосредственного перебора.
Библиогр. 10.

Ключевые слова: функциональное булево уравнение, выполнимость, сложность.

Фёдорова Валентина Сергеевна ¹
1. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 119991 Москва, Россия
е-mail: FedorovaVS@cs.msu.ru

Статья поступила 18 июня 2012 г.

Литература

[1] Ахо А. В., Сети Р., Ульман Д. Д. Компиляторы: принципы, технологии и инструменты.  - М.: Вильямс, 2003.  - 768 с.

[2] Катериночкина Н. Н. Об эквивалентности некоторых вычислительных устройств // Кибернетика.  - 1970.  - № 5.  - С. 27–31.

[3] Кудрявцев В. Б., Подколзин А. С., Болотов А. А. Основы теории однородных структур.  - М.: Наука, 1990.  - 296 с.

[4] Курода С. И. Классы языков и линейно ограниченные автоматы // Кибернетический сб. Вып. 9.  - М.: Мир, 1972.  - С. 36–51.

[5] Ложкин С. А. Лекции по основам кибернетики.  - М.: Изд-во фак-та вычисл. математики и кибернетики МГУ, 2004.  - 147 с.

[6] Марченков С. С. Итерация булевых (n, n)-операторов // Вест. МГУ. Сер. 15. Вычисл. математика и кибернетика.  - 2006.  - № 4.  - С. 36–41.

[7] Марченков С. С., Фёдорова В. С. О решениях систем функциональных булевых уравнений // Дискрет. анализ и исслед. операций.  - 2008.  - Т. 15, № 6.  - С. 48–57.

[8] Мучник А. А. Добавление переводчика к статьям «Об альтернировании, I, II» // Кибернетический сб. (новая серия). Вып. 20.  - М.: Мир, 1983.  - С. 141–158.

[9] Ekin O., Foldes S., Hammer P. L., Hellerstein L. Equational characterizations of Boolean function classes // Discrete Math.  - 2000.  - Vol. 211.  - P. 27–51.

[10] Foldes S. Equational classes of Boolean functions via the HSP theorem // Algebra Univers.  - 2000.  - Vol. 44.  - P. 309–324.