Том 19, номер 3, 2012 г., Стр. 3-12

УДК 519.714
Августинович С. В., Васильев Ю. Л., Рычков К. Л. 
Формульная сложность тернарной линейной функции

Аннотация:
Установлено, что сложность реализации в классе обобщённых (троичных) π-схем троичного счётчика кратности 3, зависящего от трёх переменных, равна 18.
Библиогр. 6.

Ключевые слова: сложность, обобщённые π-схемы, тернарная линейная функция.

Августинович Сергей Владимирович ^1,2
Васильев Юрий Леонидович ¹
Рычков Константин Леонидович ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: avgust@math.nsc.ru, vas@math.nsc.ru, rychkov@math.nsc.ru

Статья поступила 11 июля 2011 г.
Исправленный вариант — 30 ноября 2011 г.

Литература

[1] Рычков К. Л. Модификация метода В. М. Храпченко и применение её к оценкам сложности $\pi$-схем для кодовых функций // Дискрет. анализ. Вып. 42. — 1985. — С. 91–98.

[2] Рычков К. Л. О нижних оценках сложности параллельно-последовательных контактных схем, реализующих линейные булевы функции // Сиб. журн. исслед. операций. — 1994. — Т. 1, № 4. — С. 33–52.

[3] Рычков К. Л. О сложности обобщённых контактных схем // Дискрет. анализ и исслед. операций. — 2009. — Т. 16, № 5. — С. 78–87.

[4] Рычков К. Л. Нижняя оценка сложности реализации в классе $\pi$-схем $q$-ичного счётчика кратности $q$ // Дискрет. анализ и исслед. операций. — 2010. — Т. 17, № 6. — С. 68–76.

[5] Храпченко В. М. О сложности реализации линейной функции в классе $\pi$-схем // Мат. заметки. — 1971. — Т. 9, № 1. — С. 35–40.

[6] Храпченко В. М. Об одном методе получения нижних оценок сложности $\pi$-схем // Мат. заметки. — 1971. — Т. 10, № 1. — С. 83–92.