О характеристическом свойстве одного класса нормализованных формул, реализующих линейные булевы функции | Sciact - Система учета научной деятельности ИМ СО РАН

О характеристическом свойстве одного класса нормализованных формул, реализующих линейные булевы функции Научная публикация

Журнал

Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304

Вых. Данные

Год: 2024, Том: 21, Номер: 2, Страницы: 1522-1548 Страниц : 27 DOI: 10.33048/semi.2024.21.097

Ключевые слова

boolean functions, π-circuits, normalized formulas, lower bounds on complexity, formula representations, Π-partitions.

Авторы

Рычков К.Л. ¹

Организации

1	Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0017

By means of a modi cation of the method proposed by S. V. Yablonsky for constructing an economical (hypothetically minimal) normalized formula (Π-circuit) that calculates a given linear Boolean function, a whole class of similar formulas was constructed the class of so-called optimal perfect normalized formulas. Presumably it is the class of all minimal normalized formulas that compute this function. To prove this conjecture, we consider extending this class to the class of perfect normalized formulas that also compute the same function. It is established that a normalized formula is perfect if and only if it has a perfect representation on the own rectangle of the speci ed function.

Рычков К.Л.
О характеристическом свойстве одного класса нормализованных формул, реализующих линейные булевы функции
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2024. Т.21. №2. С.1522-1548. DOI: 10.33048/semi.2024.21.097

Поступила в редакцию:	27 авг. 2024 г.
Опубликована в печати:	31 дек. 2024 г.
Опубликована online:	31 дек. 2024 г.

Нет идентификаторов

Пока нет цитирований