13:17
Как математик решил задачу, которая озадачивала компьютерщиков в течение 30 лет

1 июля математик из Университета Эмори Хао Хуан спокойно доказал теорему — и миры математики и информатики взревели. В элегантном аргументе, изложенном на шести страницах, Хуан недвусмысленно доказал гипотезу чувствительности, которая десятилетиями была занозой в боку у компьютерщиков.
Доказательство воспламенило матосферу. “Удивительно короткая и красивая", - написал в своем блоге Гил Калай, математик из Еврейского университета в Иерусалиме. Доказательство “показывает, что люди все еще могут найти простые доказательства глубоких, открытых вопросов”, - говорит Крис Мур, компьютерный ученый и математик из Института Санта-Фе.
Многие мыслители на протяжении почти 30 лет занимались этой проблемой. Но пока не появился Хуан, это оставалось математическим зудом, который никто не мог почесать — все знали, где он находится, но просто не могли до него дотянуться.

Гипотеза относится к математическим структурам, называемым булевыми функциями, которые преобразуют несколько двоичных входов — 0 и 1, например, или “истинные” и “ложные” — в один двоичный выход. Вы можете подбросить монету 10 раз и определить Булеву функцию для вывода “1”, Если вы получите хотя бы одну голову, и “0” в противном случае.
Это может показаться абстрактным, но булевы идеи необходимы для современного технологического ландшафта, потому что они позволяют компьютерам вычислять. Транзисторы-это в основном переключатели включения/выключения только с одним из двух значений. Но компьютерщики хотели узнать больше о сложности этих функций. Например: на данном шаге функции, сколько входов вы должны были бы перевернуть, чтобы изменить выход? Численный ответ на этот вопрос, который затем распространяется на всю функцию, грубо говоря, называется чувствительностью.
Чувствительность - это нечто особенное. Существуют и другие способы оценки сложности булевых функций, но все они, как известно, связаны друг с другом математически. Чувствительность, однако, всегда была исключением. Гипотеза чувствительности, в основном, описывает, как эта мера могла бы вписаться в математическое семейство. Это имело смысл, что он должен быть включен, но на самом деле доказать, как он принадлежал, было более сложным делом.
Хуан говорит, что обманчивая простота проблемы впервые вызвала его интерес в 2012 году. “Каждый раз, когда я решал поднять его снова, я проводил три или четыре дня и никуда не уходил”, - говорит он. - Это мой подход ко многим проблемам.” Он думает, что потратил на это сотни часов в течение многих лет.
Прорыв Хуана произошел в июне прошлого года теплой ночью в Мадриде, где он отсиживался в гостиничном номере с шумным кондиционером. Ему следовало бы закончить мучительную процедуру подачи заявки на грант, но вместо этого он поймал себя на том, что снова думает о чувствительности. Как и другие математики до него, он считал, что наиболее естественным способом работы с двоичными входами булевых функций было рассматривать их как координатные точки, углы воображаемого вида многомерного куба. Двадцать семь лет назад математик и компьютерщик показали, что если взять набор хотя бы из половины этих точек и найти связи между ними, то можно доказать гипотезу о чувствительности. И вот что сделал Хуан: он использовал инструменты из области линейной алгебры, чтобы доказать это утверждение 1992 года. После этого он написал свою работу, разместил ее в интернете, и эксперты в равной степени удивлялись недвусмысленным аргументам его доказательства и его компактной, элегантной структуре.

Хуан не удивлен, что потребовался математик, чтобы решить проблему информатики. “Теоретическая информатика-это абстрактная математика", - говорит он, и эта проблема показывает связь. “Компьютерщики часто нуждаются в проблемах, чтобы иметь приложения, но для нас, математиков, мы заботимся об элегантности и о том, можно ли красиво сформулировать проблему.”

Похожие материалы:

Так же рекомендуем посмотреть:

Любопытные дети: как мы можем сказать, когда вулкан собирается извергнуться?


Эксперты: стадный иммунитет - это "опасный" и "ущербный" подход


1 из 4 американцев не моют руки регулярно

Категория: Тайны / Новости / Гипотеза / Наука | Просмотров: 80 | Добавил: admin | Теги: функция, чувствительность, объект исследование, самые гипотезы, проблема, Гипотеза, гипотезы происхождения, Математик, метод исследование, гипотеза чувствительности, шокирующие гипотезы | Рейтинг: 0.0/0
Всего комментариев: 0
avatar