Гипотеза «чувствительности» ставила в тупик многих выдающихся специалистов по информатике, но её новое доказательство оказалось настолько простым, что один исследователь смог свести его к единственному твиту
Опубликованная этим летом работа ставит точку в почти 30-летней истории гипотезы, касающейся структуры фундаментальных строительных блоков компьютерных схем. Эта гипотеза «чувствительности» годами ставила в тупик многих выдающихся специалистов по информатике, но её новое доказательство оказалось настолько простым, что один исследователь смог свести его к единственному твиту.
«Эта гипотеза была одной из самых раздражающих и позорных открытых задач во всей комбинаторике и теоретической информатике», — писал в своём блоге Скот Ааронсон из Техасского университета в Остине. «Список людей, пытавшихся доказать её, и не сумевших сделать это, представляет собой список самых выдающихся людей в дискретной математике и теоретической информатике», — добавил он в емейле.
Эта гипотеза связана с булевыми функциями — правилами преобразования строк входящих битов (нулей и единиц) в единственный бит. Одно такое правило выдаёт 1, когда все входящие биты равны 1, и 0 в другом случае; другое правило выдаёт 0, если в строке содержится чётное количество единиц, и 1 в другом случае. Каждая компьютерная схема является некоей комбинацией булевых функций, что делает их «строительным материалом всего, что делается в информатике», — сказал Рокко Серведио из Колумбийского университета.
С годами в информатике было разработано много способов измерения сложности заданной булевой функции. Каждая меря использует свой аспект того, как информация входящей строки определяет бит на выходе. К примеру, «чувствительность» булевой функции, грубо говоря, обозначает вероятность того, что перемена единственного бита на входе изменит бит на выходе. А «сложность запроса» подсчитывает, сколько нужно запросить входящих битов для того, чтобы уверенно знать, каков будет выходящий.
Каждая мера даёт свою уникальную точку зрения на структуру булевой функции. Однако специалисты по информатике обнаружили, что практически все эти меры укладываются в универсальную платформу, и что по значению одной из них можно примерно судить о значении других. И только одна мера сложности не укладывалась в эту схему: чувствительность.
В 1992 году Ноам Нисан из Еврейского университета в Иерусалиме и Марио Сегеды, сейчас работающий в университете Рутгерса, предположили, что чувствительность всё же укладывается в эту платформу. Но никто не мог этого доказать. «Этот вопрос, я бы сказал, был выдающимся в области изучения булевых функций», — сказал Серведио.
«Люди писали длинные, сложные работы, пытаясь достичь совсем небольшого прогресса», — сказал Райан О’Доннел из университета Карнеги-Меллон.
А теперь Хао Хуан, математик из университета Эмори, доказал гипотезу чувствительности при помощи гениального, но элементарного доказательства на две странички, связанного с комбинаторикой точек на кубах. «Оно прекрасно, как драгоценная жемчужина», — писала Клэр Мэтью, из французского государственного центра научных исследований в интервью по скайпу.
Ааронсон и О’Доннел назвали работу Хуана «книжным» доказательством гипотезы чувствительности, имея в виду понятие «небесной книги» Пала Эрдёша, в которую Бог записывает идеальные доказательства каждой теоремы. «Мне сложно представить, что даже Богу известно более простое доказательство теоремы чувствительности», — писал Ааронсон.
Чувствительная тема
Представьте, сказала Мэтью, что вы заполняете на бланке для получения займа в банке форму с вопросами, ответы на которые могут быть вида «да/нет». Когда вы закончите, банкир оценит результаты и скажет вам, подходите ли вы для получения займа. Этот процесс является булевой функцией: ваши ответы – это входящие биты, а решение банкира – выходящий.
Если в вашей заявке отказано, вы можете задуматься о том, могли ли вы изменить результат, соврав в одном-единственном вопросе – возможно, заявив, что вы зарабатываете больше $50 000 в год, хотя это не так. Если эта ложь изменит результат рассмотрения, информатики назовут такую булеву функцию «чувствительной» к значению определённого бита. Если, допустим, вы могли бы соврать в одном из семи мест, и каждый раз поменять тем самым результат, тогда чувствительность булевой функции оценки вашей заявки на кредит равняется семи.
Специалисты по информатике определяют общую чувствительность булевой функции как наибольшее значение чувствительности на всех возможных вариантах заполнения заявки. В некотором смысле эта мера подсчитывает, сколько вопросов будут действительно важными в большинстве пограничных случаев – в заявках, результат рассмотрения которых легче всего изменить, если немного изменить сами заявки.
Чувствительность обычно является одной из самых простых для расчёта мер сложности, однако она вовсе не является простой разъясняющей мерой. К примеру, наш банкир, вместо того, чтобы дать вам бланк на заполнение, мог бы начать с единственного вопроса, а потом использовать ваш ответ, чтобы определить, какой вопрос задать далее. Самое большое количество вопросов, которое может задать банкир перед тем, как прийти к решению, является булевой функцией сложности запроса.
Такая мера появляется в самых разных ситуациях – к примеру, доктор может захотеть отправить пациента на сбор как можно меньшего количества анализов для того, чтобы поставить диагноз, или эксперт по машинному обучению может захотеть создать алгоритм, изучающий как можно меньше свойств объекта перед тем, как тот сможет его правильно классифицировать. «Во многих ситуациях – диагностики или обучения – вам нравится, когда у основного правила низкая сложность запроса», — сказал О’Доннел.
Среди других мер – поиски простейшего способа записать булеву функцию в виде математического выражения, или подсчитать, сколько ответов банкир должен будет показать боссу, чтобы доказать, что заявка была обработана верно. Существует даже вариант сложности запроса из квантовой физики, когда банкир задаёт «суперпозицию» нескольких вопросов одновременно. Разбираясь в том, как эта мера связана с другими мерами сложности, исследователи лучше понимают ограничения квантовых алгоритмов.
Специалисты по информатике доказали существование близкой взаимосвязи всех этих мер, за исключением чувствительности. Конкретнее, они нашли, что они связаны друг с другом полиномиальной зависимостью – к примеру, одна мера может выражаться, как квадрат или куб другой. И только чувствительность упрямо сопротивлялась, не желая встраиваться в эту удобную схему классификации. Многие исследователи подозревали, что она должна к ней подходить, но не могли доказать, что не существует каких-нибудь странных булевых функций, чувствительность которых связана с другими мерами не полиномиальной, а экспоненциальной зависимостью, что в данном случае означало бы, что мера чувствительности кардинально меньше остальных.
«Этот вопрос 30 лет не давал людям спать спокойно», — сказал Ааронсон.
Загоняем решение в угол
Хуан узнал про эту гипотезу в конце 2012 года, за обедом с математиком Майклом Саксом из института передовых исследований, где Хуан был на должности постдока. Его сразу же увлекли простота и элегантность гипотезы. «И с того момента я стал одержим мыслями о ней», — сказал он.
Хуан добавил гипотезу чувствительности в «тайный список» интересовавших его задач, и когда он узнавал о каком-нибудь новом математическом инструменте, он раздумывал, не может ли тот помочь ему. «Каждый раз после публикации очередной работы я возвращался к этой задаче, — сказал он. – Конечно, я выделял время и силы на работу над более реалистичными задачами».
Хао Хуан на недавнем отдыхе в Лиссабоне
Хуан, как и многие в исследовательском сообществе, знал, что гипотезу о чувствительности можно доказать, если математикам удастся доказать другую гипотезу с более простым условием, касающуюся набора точек на кубах различных измерений. Существует естественный способ перехода от строки из нулей и единиц к точке на n-мерном кубе: просто используйте n битов в качестве координат этой точки.
К примеру, четыре двухбитных строки — 00, 01, 10 и 11 – соответствуют четырём углам квадрата на двумерной плоскости: (0,0), (0,1), (1,0) и (1,1). Точно также восемь трёхбитных строк соответствуют восьми углам трёхмерного куба, и так далее, для более высоких измерений. Булеву функцию можно считать правилом раскраски этих углов кубов двумя разными цветами (допустим, красным для 0 и синим для 1).
В 1992 году Крейг Готсман, сейчас работающий в технологическом институте Нью-Джерси и Нати Линьял из Еврейского университета поняли, что доказательство гипотезы чувствительности можно свести к ответу на простой вопрос о кубах различных измерений: если взять любое множество, состоящее из более чем половины вершин кубов, и раскрасить их в красный цвет, обязательно ли там найдётся красная точка, соединённая со многими другими красными точками (под «соединёнными» точками мы имеем в виду, что две вершины соединены общим ребром, а не расположены по диагонали).
Если в нашем подмножестве содержится ровно полвина вершин куба, они могут быть не соединены друг с другом. К примеру, среди восьми углов трёхмерного куба четыре точки,
(0,0,0), (1,1,0), (1,0,1) и (0,1,1), находятся по диагонали друг от друга. Но как только больше половины вершин куба любого измерения окрашиваются в красный цвет, среди них обязательно должны появиться связанные между собой красные точки. Вопрос в том, как распределяются эти связи? Будет ли среди этих вершин хотя бы одна с большим количеством соединений?
В 2013 году Хуан начал думать о том, что лучшим способом понять этот вопрос, возможно, будет использование стандартного метода представления сети при помощи матрицы, отслеживающей, какие из точек связаны между собой, и потом изучающей множество чисел, называющихся собственными значениями матрицы. Пять лет он периодически возвращался к этой идее, но безуспешно. «По крайней мере, благодаря тому, что я о ней думал перед сном, множество ночей мне легче было заснуть», — прокомментировал он запись в блоге Ааронсона.
Затем в 2018 году Хуан подумал об использовании теоремы чередования Коши, математического утверждения 200-летней давности, связывающей собственные значения матрицы с подматрицей, что, возможно, делает её идеальным инструментом для изучения взаимосвязи куба и подмножества его вершин. Хуан решил запросить грант у государственного научного фонда для дальнейшего изучения этой идеи.
Затем в прошлом месяце, сидя в отеле Мадрида и заполняя заявку на грант, он внезапно понял, что может продлить использование этого подхода до самого конца, просто меняя знаки у некоторых чисел из матрицы. Таким способом он смог доказать, что в любом наборе из более чем половины вершин n-мерного куба будет существовать точка, связанная, по меньшей мере, с √n других точек – и из этого результата сразу же вытекает гипотеза чувствительности.
Когда Мэтью получила по почте работу Хуана, первой её реакцией было «ой-ёй-ёй», сказала она. «Когда задача существует 30 лет и все о ней знают, то её доказательство должно быть либо очень длинным и сложным, или очень глубоким». Она открыла файл с работой, ожидая, что ничего не поймёт.
Однако доказательство оказалось достаточно простым для того, чтобы Мэтью и другие исследователи смогли переварить его в один присест. «Думаю, что уже этой осенью его будут рассказывать студентам в рамках одной лекции на каждом курсе магистра по комбинаторике», — написала она в скайпе.
Результат Хуана оказался даже более сильным, чем необходимо для доказательства данной гипотезы, и эта сила должна дать нам новые идеи по поводу мер сложности. «Она добавилась в наш инструментарий, и, возможно, поможет ответить на другие вопросы, связанные с булевыми функциями», — сказал Серведио.
Но главное, что результат Хуана позволяет прекратить все волнения по поводу того, не является ли чувствительность каким-то странным чужаком в мире мер сложности, сказал Серведио. «Думаю, что вечером, узнав об этих результатах, очень многие смогли заснуть спокойно».
Источник
