Том 16, номер 5, 2009 г., Стр. 78-87

УДК 519.714
К. Л. Рычков
О сложности обобщённых контактных схем

Аннотация:
Рассматриваются обобщения понятий контактной и параллельно-последовательной контактной схем на случай, когда переменные, приписанные контактам, могут принимать не два, как в булевом случае, а большее число значений. При этом проводимость контакта по-прежнему остаётся двузначной (контакт либо замкнут, либо разомкнут). Получены оценки сложности таких схем, реализующих функцию $f\colon\{0,1,\dots,q-1\}^n\to\{0,1\}$, которая принимает значение 1 на наборе $(\delta_1,\dots,\delta_n)\in\{0,1,\dots,q-1\}^n$, если $\delta_1+\dots+\delta_n\neq0\pmod q$.
Библиогр. 9.

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

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

Статья поступила 5 июня 2009 г.