Я изучаю сложный курс и сталкиваюсь с домашним заданием, которое не могу решить после 2-дневной борьбы ...
Ниже приведена проблема: предположим, что f - это любая функция, которая зависит от всех ее битов:другими словами, для каждой битовой позиции i есть вход x такой, что $f(x)\neq f(x^i)$. Покажите, что $s(f ) = \Omega(log n).$
Я прочитал статью о невырожденной булевой функции, но не нашел решения.
Я также нашел подсказку из учебника Сложность вычислений: современный подход, новсе еще не знаю.
Пожалуйста, помогите мне, любая услуга будет искренне оценена!