Для доказательства 30-летней гипотезы из области информатики хватило двух страничек

Опубликованная этим летом работа ставит точку в почти 30-летней истории гипотезы, касающейся структуры фундаментальных строительных блоков компьютерных схем. Эта гипотеза «чувствительности» годами ставила в тупик многих выдающихся специалистов по информатике, но её новое доказательство оказалось настолько простым, что один исследователь смог свести его к единственному твиту.

«Эта гипотеза была одной из самых раздражающих и позорных открытых задач во всей комбинаторике и теоретической информатике», — писал в своём блоге Скот Ааронсон из Техасского университета в Остине. «Список людей, пытавшихся доказать её, и не сумевших сделать это, представляет собой список самых выдающихся людей в дискретной математике и теоретической информатике», — добавил он в емейле.

Эта гипотеза связана с булевыми функциями — правилами преобразования строк входящих битов (нулей и единиц) в единственный бит. Одно такое правило выдаёт 1, когда все входящие биты равны 1, и 0 в другом случае; другое правило выдаёт 0, если в строке содержится чётное количество единиц, и 1 в другом случае. Каждая компьютерная схема является некоей комбинацией булевых функций, что делает их «строительным материалом всего, что делается в информатике», — сказал Рокко Серведио из Колумбийского университета.