Гипотеза о влиянии энтропии
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( Апрель 2011 г. ) |
В математике гипотеза о влиянии энтропии — это утверждение о булевых функциях, первоначально выдвинутое Эхудом Фридгутом и Гилем Калаи в 1996 году. [1]
Заявление
[ редактировать ]Для функции обратите внимание на его разложение Фурье
![{\displaystyle f(x)=\sum _{S\subset [n]}{\widehat {f}}(S)x_{S},{\text{ где }}x_{S}=\prod _{ я\в S}x_{i}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2a0a2404ef84334584bc5d8ea4034e90b51ef29)
Гипотеза энтропии-влияния утверждает, что существует абсолютная константа C такая, что где общее влияние определяется
и энтропия (спектра) определяется выражением
(где x log x принимается равным 0, когда x = 0).
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Фридгут, Эхуд; Калаи, Гил (1996). «Каждое свойство монотонного графа имеет четкий порог» . Труды Американского математического общества . 124 (10): 2993–3002. дои : 10.1090/s0002-9939-96-03732-x .
- Нерешенные проблемы теории чисел, логики и криптографии
- Проект «Открытые проблемы» , задачи дискретной и вычислительной геометрии