Полином Жегалкина

[Бодигрим]

Можно ли при помощи полинома Жегалкина проверить самодвойственность и монотонность булевой функции? Если да, то как?

[Xaositect]

Можно.
Есть алгоритмы, полиномиальные относительно длины полинома.
Посмотреть можно, например, тут

[Бодигрим]

Спасибо.