О сложности функций ?-значной логики в классе поляризованных полиномов

5 Заключение.

В настоящей работе получены и выносятся на защиту следующие результаты:

• Представлен быстрый алгоритм преобразования вектора значений функции к—значной логики в вектор коэффициентов ее простого поляризованного полинома (теоремы 3.1.4, 3.2.2).

• Для булевой логики показано, что некоторые периодические функции являются самыми сложными в классе поляризованных полиномов (теорема 4.1.11).

• Для трехзначной логики улучшена нижняя оценка функции Шеннона в классе поляризованных полиномов и представлены периодические функции, на которых эта оценка достигается (теоремы 4.2.9 и 4.2.10).

• Для пятизначной логики доказана вырожденность и невырожденность некоторых последовательностей периодических функций (теоремы 4.6.5 и 4.7.12).

• Для к—значной логики найден критерий невырожденности последовательностей периодических функций, сводящий вопрос о невырожденности конкретных функций к вычислительной задаче полиномиальной по значности логики к и экспоненциальной по длине периода Т (теоремы 4.4.3 и 4.4.5).

• Получена нижняя оценка сложности последовательностей невырожденных функций к—значной логики в классе поляризованных полиномов (теорема 4.4.4).

• Для к—значной логики найден критерий невырожденности семейств последовательностей периодических функций, сводящий вопрос о невырожденности семейств функций к вычислительной задаче полиномиальной по значности логики к и длине периода Т (теоремы 4.4.6 и 4.4 7).

• Для А-—значной логики показано, что периодические функции с достаточно большой длиной периода являются невырожденными в классе поляризованных полиномов (теорема 4.9.1).

1. Алексеев В. В., Вороненко A.A., Селезнева С. Н. О сложности реализации функций k-значной логики поляризованными полиномами // Труды V Международной конференции «Дискретные модели в теории управляющих систем». М.: МАКС Пресс, 2003. С. 8−9.

2. Артюхов B. JL, Копейкин Г. А., Шалыго A.A. Настраиваемые модули для управляющих логических устройств. Ленинград: Энергоиздат, 1981. 166 с.

3. Балюк А. С. Сложные в полиномиальных поляризованных формах функции алгебры логики // Тезисы докладов международной конференции по математической логике. Новосибирск, 1999. С. 9−10.

4. Баранова С. И., Скляров В. А. Цифровые устройства на программируемых СБИС с матричной структурой. М.: Радио и связь, 1986. 270 с.

5. Бибило П. Н. Синтез комбинационных ПЛМ структур для СБИС. Минск: Наука и техника, 1992. 232 с.

6. Виноградов И. М. Основы теории чисел. М.-Л., Гостехиздат, 1952. С. 29, 47−48.

7. Гаврилов Г. П., Сапоженко A.A. Задачи и упражнения по дискретной математике. М.: Физматлит, 1977. С. 52−58.

8. Денисов E.H. О сложности функций трехзначной логики в классе поляризованных полиномов. Дипломная работа, кафедра математической кибернетики, ВМиК МГУ им. Ломоносова, 2006.

9. Жегалкин И. И. Арифметизация символической логики // Мат. сборник.1928. Т.35. С.311−373.'.

10. Жегалкин И. И. Арифметизация символической логики // Мат. сборник.1929. Т.36. С.305−338.

11. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций // Дискретная математика, т. 17, вып. 3, и, 2005. С. 80−88.

12. Лидл Р., Нидеррайтер Г. Конечные поля. — М.: Мир, 1988.

13. Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики. Вып. 14 М.: Наука, 1965. С. 31−110.

14. Маркелов Н. К. Селезнева С. Н. Быстрый алгоритм построения векторов коэффициентов поляризованных полиномов к—значных функций // Тезисы докладов XV Международной конференции «Проблемы теоретической кибернетики». Казань: Отечество, 2008. С. 102.

15. Маркелов Н. К. О сложности периодических функций трехзначной логики в классе поляризованных полиномов // Материалы XVI Международной конференции (Нижний Новгород, 20—25 июня 2011 г). Изд-во Нижегородского госуниверситета, 2011. С. 301−303.

16. Маркелов Н. К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов // Вестник Московского университета. Сер. 15, Вычислительная математика и кибернетика. 2012. № 3. С. 40−45.

17. Маркелов Н. К. Критерий невырожденности периодических функций к—значной логики // Материалы X Международного семинара «Дискретная математика и ее приложения"(Москва, 18—23 июня 2012 г). С. 199−202.

18. Маркелов Н. К. О сложности в классе поляризованных полиномов периодических функций к—значной логики с периодами большой длины // Научная конференция «Тихоновские чтения», тезисы докладов (Москва, 29−31 октября 2012 г). М.: МАКС Пресс, 2012. С. 50.

19. Перязев H.A. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика, т. 34, вып. 3. 1995. С. 323vK—326. ,.

20. Разборов А. А. Нижние оценки размера схем ограниченной глубины в полном базисе, содержащем функцию логического сложения // Матем. заметки, ДАН СССР 41:4. 1987. С. 598−607.

21. Селезнева С. Н., Маркелов Н. К. Быстрый алгоритм построения векторов коэффициентов поляризованных полиномов к—значных функций // Ученые записки Казанского университета Сер. Физико-математические науки, Т. 151, вып. 2. 2009. С. 147−153.

22. Селезнева С. Н., Дайняк А. Б. О сложности обобщенных полиномов А-—значных функций / / Вестник Моск. У нив. Серия 15. Вычисл. матем. и кибернетика. 2008. С. 34−39.

23. Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами // Дискретная математика том 14, выпуск 2. 2002. С. 48−53.

24. Селезнева С. Н. О сложности поляризованных полиномов функций многозначных логик, зависящих от одной переменной // Дискретная математика том 16, выпуск 2. 2004. С. 117—120.

25. Селезнева С. Н. О сложности k-значных функций в одном классе полиномов // Проблемы теоретической кибернетики. Материалы XVI международной конференции. Нижний Новгород: Издательство Нижегородского госуниверситета, 2011. С. 430−434.

26. Супрун В. П. Табличный метод полиномиального разложения булевых функций // Кибернетика. 1987. № 1. С. 116−117.

27. В. П. Супрун, Сложность булевых функций в классе канонических поляризованных полиномов // Дискретная математика, том 5, выпуск 2. 1993. С. 111−115.

28. Шалыто А. А. Логическое управление. Методы аппаратной и программной реализации. СПб.: Наука, 2000. 780 с.

29. Яблонский С. В.

Введение

в дискретную математику. М.: Высшая школа, 2001. С. 9−42.

30. Яблонский С. В. 'Функциональные построения в к—значной логике // '.

31. Труды математического института им. В. А. Стеклова АН СССР. Т. 51. 1958. С. 5−142.

32. Aspnes J., Beigel R., Furst M., Rudich S. The expressive power of voting polynomials // Combinatorica, vol. 14, no. 2. 1994. P. 135−148.

33. Beigel R. The polynomial method in circuit complexity // Structures in Complexity Theory: 8 th Annual Conference. 1993. P. 82−95.i.

34. Beigel R., Reingold N., Spielman D. The perceptron strikes back // Proceedings of the Sixth Conference on Structure in Complexity Theory. 1991. P. 286−291.

35. Efremenko K. 3-query locally decodable codes of subexponential length //.

36. Accepted to the 41 st Annual Symposium on the Theory of Computing *.

37. STOC'09). ACM. 2009. P. 39−44.

38. GopalanP., Shpilka A., Lovett S. The Complexity of Boolean Functions in Different Characteristics // Computational Complexity vol. 19, no. 2. 2010. P. 235−263.

39. Even S., Kohavi I., Paz A. On minimal modulo 2 sums of products for switching functions // IEEE Trans. Elect. Comput. 1967. P. 671−674.i.

40. Falkowski B.J., Rahardja S. Efficient computation of quaternary fixed polarity Reed-Muller expansions // IEE Proc. Comput. Digit. Tech., Vol. 142, No. 5. 1995. P. 345−352.

41. Grolmusz V., Superpolynomial size set-systems with restricted intersectionsmod 6 and explicit Ramsey graphs // Combinatorica, vol. 20, no. 1. 2000. P., 71.86.

42. Gopalan P. Constructing Ramsey graphs from Boolean function representations // In Proceedings of the 21 st IEEE Conference on Computational Complexity (CCC'06). 2006. P. 115−128.797.7−6—784. — *.

43. Jankovic D., Stankovic R.S., Moraga C. Optimization of arithmetic expressions using the dual polarity property // 1st Balkan Conference in Informatics, BCI 2003, Thessaloniki, Greece. 2003. P. 402−410.

44. Klivans A. Servedio R. Learning DNF in time 2°(nl/3) //in Proceedings of t the 33rd Annual Symposium on Theory of Computing (STOC'Ol). 2001. P. 258−265.

45. Kushilevitz E., Mansour Y. Learning decision trees using the Fourier spectrum // SIAM J. on Computing, vol. 22, no. 6. 1993. P. 1331−1348.

46. Linial N., Mansour Y., Nisan N. Constant depth circuits, Fourier transform and learnability // Journal of the ACM vol. 40, no. 3. 1993. P. 607−620.

47. Mac Williams F., Sloan N. The Theory of Error-Correcting Codes. North-Holland, 1977. 762 p.

48. Minsky M. Papert S. Perceptrons: an Introduction to Computational Geometry. MIT Press, 1968. 292 p.

49. Mossel E., O’Donnell R., Servedio R. Learning juntas //In Proceedings of i the 35 th Annual ACM Symposium on the Theory of Computing (STOC'03).2003. P. 206−212.

50. Muller D. E. Application of Boolean algebra to switching circuit design and to error detection // IRE Trans. Electron. Comput. EC-3. 1954. P. 6−12.

51. Reed I. S. A class of multiple-error-correcting codes and the decoding scheme // IRE Trans, on Inform. Theory. 1954. P. 38−49.V.

52. Shannon C.E. The synthesis of two-terminal switching circuits. // Bell Syst. Techn, vol. 28, no. 1. 1949. P. 59−98.

53. Smolensky R. Algebraic methods in the theory of lower bounds for Boolean circuit complexity //In Proceedings of the 19 th Annual ACM Symposiumon Theoretical Computer Science (STOC'87). 1987. P. 77−82. ,.

54. Sasao T. Multiple-Valued Decomposition of Generalized Boolean Functions and the Complexyty of Programmable Logic Arrays // IEEE Trans, on Comput, vol. 30, no. 9. 1981. P. 633−645.

55. Sasao T., Besslich P. On the complexity of mod-2 sum PLA’s // IEEE Trans, on Comput, vol. 39, no. 2. 1990. P. 262−266.

56. Wood R.A. A Higt Density Programmable Logic Array Chip // IEEE Trans, vol. 29, no. 9. 1979. P. 602−608.i.