Гипотеза о чувствительности The Sensitivity Conjecture является одной из самых важных и сбивающих с толку открытых проблем теоретической информатики на протяжении почти трех десятилетий. Похоже, что она наконец встретит свое решение благодаря работе Хао Хуанга, доцента математики в Университете Эмори.
Хуанг представит доказательство гипотезы о чувствительности на международной конференции по случайным структурам и алгоритмам International Conference on Random Structures and Algorithms, которая состоится в Цюрихе, Швейцария, 15-19 июля.
«Я занимаюсь этой проблемой с 2012 года, - говорит Хуанг, - но ключевая идея возникла у меня примерно неделю назад. Я наконец-то определил правильный инструмент для ее решения».
Хуанг разместил доказательство на своей домашней странице, и вскоре он вызвал ажиотаж в социальных сетях среди математиков и учёных в области информатики, которые высоко оценили его удивительную лаконичность и простоту.
Гипотеза о чувствительности относится к логическим данным, которые отображают информацию в формате истинно-ложное или двоичное значение 1-0. Булевы функции играют важную роль в теории теорией сложности вычислений, а также в разработке схем и микросхем для цифровых компьютеров.
«В математике булева функция является одним из самых основных дискретных предметов - точно так же, как числа, графики или геометрические фигуры», - объясняет Хуанг.
Существует много показателей сложности булевой функции, и известно, что почти все из них, включая сложность дерева решений, сложность сертификата, сложность рандомизированных запросов и многие другие, известны как полиномиально связанные. Однако существует один неизвестный случай, так называемая чувствительность булевой функции, которая измеряет, насколько чувствительна функция при изменении одного входа за раз.
В 1994 году математики Ноам Нисан (Noam Nisan) и Марио Сегеди (Mario Szegedy) предложили гипотезу чувствительности относительно этого неизвестного случая.
«Их гипотеза говорит, что чувствительность булевой функции также полиномиально связана с другими мерами», - говорит Хуанг.
Хуанг разработал алгебраический метод доказательства гипотезы. «Я надеюсь, что этот метод также может быть применен к другим комбинаторным и сложным проблемам, важным для информатики», - говорит он.
Источник: Phys.org / Emory University
