Том 19, номер 5, 2012 г., Стр. 35-46

УДК 519.7
Золотых Н. Ю., Чирков А. Ю.  
О верхней оценке мощности минимального разрешающего множества пороговой функции

Аннотация:
Предлагается новое необходимое и достаточное условие принадлежности точки минимальному разрешающему множеству пороговой функции $k$-значной логики. Это позволяет выделить большой подкласс пороговых функций, для которых мощность минимального разрешающего множества при фиксированном числе переменных $n$ ограничена сверху полиномом от $\log_2k$ степени $n-2$.
Ил. 1, библиогр. 17.

Ключевые слова: пороговая функция, разрешающее множество, свойство разделённости.

Золотых Николай Юрьевич ¹
Чирков Александр Юрьевич ¹
1. Нижегородский гос. университет им. Н. И. Лобачевского,
пр-т Гагарина, 23, корп. 2, 603950 Н. Новгород, Россия
е-mail: zolotykh@vmk.unn.ru, chirkov@vmk.unn.ru

Статья поступила 23 октября 2011 г.
Исправленный вариант — 23 марта 2012 г.

Литература

[1] Веселов С. И., Чирков А.Ю. Оценки числа вершин целых полиэдров // Дискрет. анализ и исслед. операций. Сер. 2. — 2007. — Т. 14, № 2. — C. 14–31.

[2] Вировлянская М. А., Золотых Н. Ю. Верхняя оценка средней мощности минимального разрешающего множества пороговой функции многозначной логики // Вестн. Нижегородск. гос. ун-та им. Н. И. Лобачевского. Математическое моделирование и оптимальное управление. — Н. Новгород.: Изд-во ННГУ, 2003. — С. 238–246.

[3] Вировлянская М. А., Золотых Н. Ю. О мощности разрешающего множества пороговой функции многозначной логики // Мат. XIV Междунар. шк.-семинара «Синтез и сложность управляющих систем». — Н. Новгород: Изд-во Нижегородск. гос. пед. ун-та, 2003. — C. 20–21.

[4] Золотых Н. Ю. О сложности расшифровки пороговых функций, зависящих от двух переменных // Мат. XI Межгос. шк.-семинара «Синтез и сложность управляющих систем». Ч. I. — М.: Изд-во Центра прикл. исслед. при мех.-мат. фак. МГУ, 2001. — C. 74–79.

[5] Золотых Н.Ю. Оценки мощности минимального разрешающего множества пороговой функции многозначной логики // Математические вопросы кибернетики. Вып. 17. — М.: Физматлит, 2008. — C. 159–168.

[6] Золотых Н. Ю. Новая модификация метода двойного описания для построения остова многогранного конуса // Журн. вычисл. математики и мат. физики. — 2012. — Т. 52, № 1. — C. 153–163.

[7] Золотых Н. Ю., Шевченко В. Н. Расшифровка пороговых функций $k$-значной логики // Дискрет. анализ и исслед. операций. — 1995. — Т. 2, № 3. — C. 18–23.

[8] Золотых Н. Ю., Шевченко В. Н. О нижней оценке расшифровки пороговых функций $k$-значной логики // Журн. вычисл. математики и мат. физики. — 1999. — Т. 39, № 2. — C. 346–352.

[9] Схрейвер А. Теория линейного и целочисленного программирования. — М.: Мир, 1991. — 360 c.

[10] Шевченко В. Н. О числе крайних точек в целочисленном программировании // Кибернетика. — 1981. — № 2. — C. 133–134.

[11] Шевченко В. Н. О некоторых функциях многозначной логики, связанных с целочисленным программированием // Методы дискретного анализа в теории графов и схем. Вып. 42. — Новосибирск: Ин-т математики СО АН СССР, 1985. — C. 99–108.

[12] Шевченко В. Н. Качественные вопросы целочисленного программирования. — М.: Физматлит, 1995. — 192 c.

[13] Шевченко В. Н., Золотых Н. Ю. О сложности расшифровки пороговых функций $k$-значной логики // Докл. РАН. — 1998. — Т. 362, № 5. — C. 606–608.

[14] Antony M., Brightwell G., Shawe-Taylor J. On exact specification by labeled examples // Discrete Appl. Math. — 1995. — Vol. 61, N 1. — P. 1–25.

[15] Cook W., Hartmann M., Kannan R., McDiarmid C. On integer points in polyhedra // Combinatorica. — 1992. — Vol. 12, N 1. — P. 27–37.

[16] Hegedüs T. Geometrical concept learning and convex polytopes // Proc.7th Ann. ACM Conf. Computational Learning Theory (COLT’94). — New York: ACM Press, 1994. — P. 228–236.

[17] Hegedüs T. Generalized teaching dimensions and the query complexity of learning // Proc. 8th Ann. ACM Conf. Computational Learning Theory (COLT’95). — New York: ACM Press, 1995. — P. 108–117.