• Октябрь 22, 2007
  • Владимир Подольский
  • Однородная по степени экспоненциальная нижняя оценка на веса персептронов
  • по работе Бейгеля
  • Аннотация
  • Пусть x_1, ..., x_n -- булевы переменные. Персептроном степени d называется булева функция, равная знаку многочлена с целыми коэффициентами степени не выше d от переменных x_1, ..., x_n. Весом персептрона называется максимум абсолютных значений его коэффициентов.

    Известна верхняя оценка на вес персептрона степени 1: всякий функция, вычислимая персептроном степени 1, вычислима персептроном степени 1 с весом n^n.

    Будет построена функция, вычислимая персептроном степени 1 (с экспоненциальным весом), но не вычислимая персептроном полилогарифмической степени с субэкспоненциальным весом. То есть, для вычисления функции персептроном требуются экспоненциальные веса, даже если разрешить полилогарифмическую степень.