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

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

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