На двух страницах была решена загадка компьютерной науки, которой уже несколько десятков лет
В статье, размещенной в Интернете в этом месяце, была решена гипотеза почти 30-летней давности о структуре фундаментальных строительных блоков компьютерных схем. Эта гипотеза о «чувствительности» на протяжении многих лет ставила в тупик многих видных ученых-компьютерщиков, однако новое доказательство настолько просто, что один исследователь суммировал его в одном твите.
«Эта гипотеза стала одной из самых разочаровывающих и смущающих открытых проблем во всей комбинаторике и теоретической информатике», — написал Скотт Ааронсон из Техасского университета в Остине в своем блоге. «Список людей, которые пытались решить ее и потерпели неудачу, похож на список тех, кто есть кто в дискретной математике и теоретической информатике», — добавил он в электронном письме.
Гипотеза касается булевых функций, правил преобразования строки входных битов (0 и 1) в один выходной бит. Одним из таких правил является вывод 1 при условии, что любой из входных битов равен 1, и 0 в противном случае; другое правило состоит в том, чтобы выводить 0, если в строке четное количество единиц, и 1 в противном случае.
Каждая компьютерная схема представляет собой некоторую комбинацию булевых функций, что делает их «кирпичиками и раствором всего, что вы делаете в компьютерных науках», — сказал Рокко Серведио из Колумбийского университета.
На протяжении многих лет ученые-компьютерщики разработали множество способов измерения сложности данной булевой функции. Каждая мера фиксирует отдельный аспект того, как информация во входной строке определяет выходной бит. Например, «чувствительность» булевой функции отслеживает, грубо говоря, вероятность того, что переключение одного входного бита изменит выходной бит. А «сложность запроса» вычисляет, сколько входных битов вы должны запросить, прежде чем сможете быть уверены в результате.
Каждая мера предоставляет уникальное окно в структуру булевой функции. Тем не менее ученые-компьютерщики обнаружили, что почти все эти показатели вписываются в единую структуру, так что значение любого из них является грубым показателем значения других. Только одна мера сложности не подходила: чувствительность.
В 1992 году Ноам Нисан из Еврейского университета в Иерусалиме и Марио Сегеди, ныне из Университета Рутгерса, предположили, что чувствительность действительно укладывается в эти рамки. Но никто не мог этого доказать. «Это, я бы сказал, вероятно, был нерешенным открытым вопросом в изучении булевых функций», — сказал Серведио.
«Люди писали длинные и сложные статьи, пытаясь добиться хоть малейшего прогресса, — сказал Райан О’Доннелл из Университета Карнеги-Меллона.
Теперь Хао Хуанг, математик из Университета Эмори, доказал гипотезу о чувствительности с помощью гениального, но элементарного рассуждения на двух страницах о комбинаторике точек на кубах. «Он просто прекрасен, как драгоценная жемчужина», — написала Клэр Матье из Французского национального центра научных исследований в интервью по Skype.
Ааронсон и О’Доннелл назвали статью Хуанга «книжным» доказательством гипотезы о чувствительности, имея в виду идею Пола Эрдёша о небесной книге, в которой Бог записывает идеальное доказательство каждой теоремы.
«Мне трудно представить, что даже Бог знает, как доказать гипотезу о чувствительности более простым способом, чем этот», — писал Ааронсон.
Деловой вопрос
Представьте себе, сказал Матье, что вы отвечаете на ряд вопросов да/нет в заявлении на получение банковского кредита. Когда вы закончите, банкир оценит ваши результаты и сообщит вам, имеете ли вы право на получение кредита. Этот процесс является булевой функцией: ваши ответы — это входные биты, а решение банкира — выходной бит.
Если ваша заявка будет отклонена, вы можете задаться вопросом, могли ли вы изменить результат, солгав в одном вопросе — например, заявив, что вы зарабатываете более 50 000 долларов, хотя на самом деле это не так. Ученые-компьютерщики говорят, что если бы эта ложь изменила результат, логическая функция «чувствительна» к значению этого конкретного бита. Если, скажем, есть семь разных лжи, которые вы могли бы сказать, каждая из которых по отдельности изменила бы результат, то для вашего кредитного профиля чувствительность булевой функции равна семи.
Как решать буквенные головоломки
FutureLearn использует куки-файлы, чтобы улучшить ваше взаимодействие с веб-сайтом. Все файлы cookie, кроме строго необходимых, в настоящее время отключены для этого браузера. Включите JavaScript, чтобы применить настройки файлов cookie для всех необязательных файлов cookie. Вы можете ознакомиться с политикой FutureLearn в отношении файлов cookie здесь.
Посмотрите этот пример, чтобы узнать, как решать буквенные головоломки
Я рекомендую прочитать это, прежде чем смотреть видео… Есть ключевые элементы для решения большинства алфавитных задач.
- Во многих случаях результатом задачи на сложение является одна цифра длиннее (по длине цифры), чем слагаемые – добавленные числа. Если слагаемых всего два, это означает, что лишняя цифра — это число 1.
Давайте рассмотрим очень простую азбуку: ME+ME=BEE
Буква B должна представлять цифру 1, так как при сложении двух двузначных чисел невозможно получить число больше 198.
Это происходит, когда оба слагаемых равны 99. Поскольку М и Е — два разных числа, они наверняка будут даже меньше 99! В любом случае разряд сотен в сумме, представленной в нашем примере буквой B, должен быть равен 1.
- В двух алфавитах слагаемых могут быть столбцы, содержащие одну и ту же букву как в слагаемом, так и в результате. Если такой столбец является столбцом единиц, эта буква должна быть 0. В противном случае это может быть либо 0, либо 9 (и тогда есть перенос).
В алфавитном порядке: ME+ME=BEE столбец цифр единицы: E+E=E Есть только одна цифра, которая обладает тем свойством, что при добавлении ее самой к себе вы получаете ту же цифру, что и результат – нуль! Только сумма двух нулей равна нулю, поэтому Е должно быть равно 0.
Таким образом, решение этого алфавитного числа: B=1, E=0, M=5: 50+50=100.
Вот несколько советов по решению более сложной азбуки.
Если имеется более двух дополнений, применяются те же правила, но их необходимо скорректировать, чтобы учесть другие возможности.
Если в столбце единиц четыре одинаковых буквы (одна из них сумма), то теперь эта буква может быть: 0 или 5 (потому что 5+5+5=15). Если в другом столбце есть четыре одинаковых буквы (одна из них сумма), эта буква теперь может быть: 0 или 5 (без переноса), 4 или 9(нести 2). Четыре одинаковые буквы в столбце, отличном от столбца единиц, означают, что 1 нельзя было перенести (почему бы и нет?). Это правило может быть выработано и для более чем 3 слагаемых…- Целесообразно превратить задачи на вычитание в задачи на сложение, добавив результат к меньшему сложению, чтобы получить большее.
- Столкнувшись с несколькими вариантами письма, пробуйте один, пока либо не получите правильный ответ, либо не найдете противоречие.
Если в столбце единиц четыре одинаковых буквы (одна из них сумма), то теперь эта буква может быть: 0 или 5 (потому что 5+5+5=15). Если в другом столбце есть четыре одинаковых буквы (одна из них сумма), эта буква теперь может быть: 0 или 5 (без переноса), 4 или 9(нести 2). Четыре одинаковые буквы в столбце, отличном от столбца единиц, означают, что 1 нельзя было перенести (почему бы и нет?). Это правило может быть выработано и для более чем 3 слагаемых…Теперь давайте рассмотрим немного более продвинутый криптарифм. В этом видео показано, как решить алфавитную задачу: НЕТ + ОРУЖИЕ + НЕТ = ОХОТА. Обратите внимание на «аккуратное» предложение: «Нет ружья, нет охоты!».
Эта статья из бесплатного онлайн-ресурса
Математические головоломки: криптарифмы, символы и секретные коды
Создано
Присоединяйся сейчас
Мы предлагаем широкий выбор курсов от ведущих университетов и учреждений культуры со всего мира.