Comments 60
Матан!
Сделать это так, чтобы он ничего не почувствовал.
Насколько я понял суть гипотезы в том, что для n-мерного входа, чувствительность булевой функции по крайней мере корень из n , но повторяющиеся тезисы в статье и бессмысленные в ставки мешают понять это.
Правильная формулировка такая: чувствительность не меньше корня из deg(f) (степени функции).
А что такое степень надо говорить отдельно.
Любую булеву функцию можно представить в виде полинома. Я не уверен, что прав, но вроде бы имеется в виду Полином Жегалкина. Собственно deg(f), т.е. степень функции — это степень этого полинома, т.е. максимальная степень его слагаемых.
Вообще парень доказал штуку, которая довольно просто формулируется в терминах графов. В n-мерном кубическом графе любой подграф степени 2^(n-1)+1 (т.е. имеющий больше половины вершин исходного графа) имеет вершину степени не меньше чем sqrt(n).
Правда я понятия не имею, как из этой теоремы следует теорема чувствительности, но вроде как это известный переход, на который ссылается автор. Только разобраться надо.
Там ещё пара страниц доказательства, которые я пожалуй пока не осилю)
Это как раз тот момент, когда специалист с профильным университетским дипломом может спокойно признать, что оно выглядит как иностранный язык.
проще говоря — удалось доказать математическую зависимость "меры чуствительности" относительно прочих мер (т.е. "не меньше чем корень" и т.д.) и теперь у математиков будет на одну лекцию больше рассказа для студентов (заодно и мотивация :) "вот видите — как просто, вы тоже можете так, если будете больше думать")
гипотеза «чувствительности» ставила в тупик многих выдающихся специалистов по информатике, но её новое доказательство оказалось настолько простым, что один исследователь смог свести его к единственному твитуЧтобы «статья» была подлиннее, давайте повторим заголовок.
Чтобы «статья» была подлиннее, давайте повторим заголовок.
Эта статья могла бы быть длиннее, если бы повторяла заголовок — писал в комментариях к этой статье пользователь GeMir с хабрахабра в интернете
В 2019 году GeMir, сейчас находящийся на хабрахабре, предположил, что статья могла бы быть длиннее, если бы повторяла заголовок. «Этот вопрос, я бы сказал, был выдающимся в области написания статей», — сказал GeMir.
«Люди писали длинные, сложные статьи, пытаясь достичь совсем небольшого удлинения», — сказал GeMir с хабрахабра.
Чтобы «статья» была подлиннее, давайте повторим заголовок. — сказал GeMir
- «Эта гипотеза была одной из самых раздражающих и позорных открытых задач во всей комбинаторике и теоретической информатике», — писал в своём блоге Скот Ааронсон из Техасского университета в Остине.
- В 1992 году Ноам Нисан из Еврейского университета в Иерусалиме и Марио Сегеды, сейчас работающий в университете Рутгерса, предположили, что чувствительность всё же укладывается в эту платформу. Но никто не мог этого доказать. «Этот вопрос, я бы сказал, был выдающимся в области изучения булевых функций», — сказал Серведио.
- «Люди писали длинные, сложные работы, пытаясь достичь совсем небольшого прогресса», — сказал Райан О’Доннел из университета Карнеги-Меллон.
- «Этот вопрос 30 лет не давал людям спать спокойно», — сказал Ааронсон.
PS: На самом деле это просто жутко бесящий "западный" науч-поп стиль.
Я хотел сказать что такой стиль написания научно-популярных статей очень част на западе.
"Часто можно встретить научно популярную статью или фильм которая повторяет одно и то же несколько раз" — сказал я сегодня.
Прям как эталонный студенческий диплом.
По-моему, вполне нормально:
Эта гипотеза связана с булевыми функциями — правилами преобразования строк входящих битов (нулей и единиц) в единственный бит.
^ Гипотеза, о которой будут говорить — про хэш-функции (так, MD5 хэширует произвольный файл в набор из 128 бит, а описываемая — в набор, если его так можно назвать, из 1 бита).
Одно такое правило выдаёт 1, когда все входящие биты равны 1, и 0
^ Пример одного из таких алгоритмов
другом случае; другое правило выдаёт 0, если в строке содержится чётное количество единиц, и 1 в другом случае.
^ Пример другого алгоритма того же класса
Каждая компьютерная схема является некоей комбинацией булевых функций, что делает их «строительным материалом всего, что делается в информатике», — сказал Рокко Серведио из Колумбийского университета.
^ А вот это, конечно, хабрааудитории общеизвестно.
P.S. Задумался. Сдаётся мне, функции коррекции ошибок следует искать среди функций с минимальной чувствительностью...
Гипотеза, о которой будут говорить — про хэш-функцииХэш-функция с двумя значениями? Полезно. Если уж хочется зачем-то дать синоним булевой функции, то это называется «предикат».
Пример одного из таких алгоритмовЭтот «алгоритм» называется AND, конъюнкция
Пример другого алгоритма того же классаА этот XOR.
То есть, по сути, в том абзаце дается сначала примерное определение булевых функций «на пальцах». Затем приводят два примера: and и xor. А затем следует действительно какое-то капитанское утверждение.
Хэш-функция с двумя значениями? Полезно.
Хэш-функция — это любая функция, (неуникально) отображающая пространство бОльшего размера на пространство меньшего размера. Всё остальное (в том числе и рамзмер пространства) — детали. Случай, когда выходное пространство имеет размер 1 бит — вырожденный, но всё равно легитимный случай.
Этот «алгоритм» называется AND, конъюнкция… А этот XOR.
Несущественные детали. Аффтар всего-навсего приводит примеры. Примеры, как в большинстве случаев, упрощены до невозможности, чтобы понятно было даже самому распоследнему дебилу.
Вы в математику вообще умеете? Там очень многое основывается на предельных случаях (утрируя, "докажем теорему для N участников… рассмотрим случай, когда N=1...") и индукции.
Хэш-функция — это любая функция, (неуникально) отображающая пространство бОльшего размера на пространство меньшего размер
Я не буду комментировать это определение, только замечу, что булева функция f(b) = b ему не соотвествует.
Вы в математику вообще умеете? Там очень многое основывается на предельных случаях (утрируя, «докажем теорему для N участников… рассмотрим случай, когда N=1...») и индукции.
Ну да, самое удачное место спросить собеседника о том, знает ли он, что такое индукция — это в комментариях к статье о доказательстве математической гипотезы.
Я не буду комментировать это определение
Хеш-функция — функция, осуществляющая преобразование массива входных данных произвольной длины в (выходную) битовую строку установленной длины. В данном случае "установленная длина" = 1 бит.
только замечу, что булева функция f(b) = b ему не соотвествует.
Жду объяснений, как именно не соответствует. Как я уже писал выше, это просто частный случай хеш-функции: из пространства размера X переводит в пространство размера 1. Практическая ценность, конечно, близка к нулю (но выше я уже упоминал, например, коды обнаружения/коррекции ошибок: результат "свёртки" = 0 — ошибки нет, результат 1 = ошибка есть).
Хеш-функция — функция, осуществляющая преобразование массива входных данных произвольной длины в (выходную) битовую строку установленной длины.Можно подать входные данные на набор булевых функций, где каждая функция отвечает за свой выходной бит в выходных данных, и получить таким образом выход любой требуемой разрядности. Или такая «сборка» уже не будет хеш-функцией?
Я не понял, кому Вы это сказали — судя по треду, мне; судя по логике — моему оппоненту. Но я с Вами полностью согласен. (Правда, такие функции могут получиться весьма сложными, но тем не менее принципиально Вы правы. Мы ведь тут не придумываем, как эффективнее функции вычислять, а всего лишь занимаемся интеллектуальным онанизмом упражнениями.)
Интуитивно предполагаю, что чувствительность у хеш-функций должна быть высокой. То есть, чувствительность можно использовать как оценку «качества» для отбора хеш-функций, порождённых, к примеру, генетическим алгоритмом.
А для перцептивных хешей чувствительность, как мне кажется, должна быть наоборот низкой, чтобы небольшие флуктуации точки в гиперкубе не меняли значение на выходе функции.
Вот хочу спросить, используют ли чувствительность для оценки хеш-функций?
Видите ли, любая функция, осуществляющая вышеописанное отображение, является, по определению, хеш-функцией. А вот является ли она хорошей хеш-функцией — это уже совершенно другой вопрос ;) И моя интуиция с Вашей согласна — (именно для повышения чувствительности в MD5 и прочих алгоритмах применяют неоднократное перемешивание битов). Вот то, что "малое изменение исходного файла вызывает значительное изменение результата" называется "чувствительностью" — это я из этой статьи узнал :)
Вот хочу спросить, используют ли чувствительность для оценки хеш-функций?
Не знаю, но мне кажется, было бы логично так делать!
Можно было написать академично: "любая булева функция может быть представлена как полином Жегалкина".
Можно написать по-простому: "комбинируя AND и XOR можно составить любое условие".
А можно написать так, как написано в статье — длинно, наукообразно, и запутанно.
А вот это, конечно, хабрааудитории общеизвестно.
Надеюсь, что всё-таки да. Особенно во втором варианте.
никто не заставляет бесполезного графомана Вячеслава переводить все, он мог бы взять пример с уважаемого Ализара, который постит новости только по сути. У Голованова стиль такой же как у убогих журналистов желтой прессы — яркий заголовок и бесполезный контент.
Если совсем нечего делать и нет свежих статей — пробегаем текст глазами в течение 10 секунд и пытаемся найти что-то интересное, а потом проходим мимо.
Если совсем нечего делать — пробегая глазами, мотаем до низа и кликаем на оригинал. Но там тоже сильно не факт, что будет интересно. Ув. SLY_G
И интересные статьи он тоже переводит. Чего стоит первая половина цикла «Спросите Итана».
Т.е. это доказательство может оказаться полезным в понимании работы мозга.
Ну и к тому же на дендритную ветку «проецируется» только одна вершина гиперкуба, а в статье оперируют множеством вершин.
Прошу прощения у математиков, постарался убрать все математические термины из объяснения.
Есть функция от нескольких булевых аргументов. Для примера пусть их будет 5. Мы хотим измерить ее чувствительность. Возьмем любой произвольный вход
f(0,1,0,1,1) = 1каждый аргумент по очереди меняем 0 -> 1, 1 -> 0
f(1,1,0,1,1) = 1
f(0,0,0,1,1) = 0
f(0,1,1,1,1) = 1
f(0,1,0,0,1) = 1
f(0,1,0,1,0) = 0
Смотрим, что функция поменяла свое значение с 1 на 0 для двух вариантов. Значит "чувствительность" этого входа 2.
Для того чтобы узнать чувствительность функции, нам нужно пробежать по каждому возможному входу (в этом случае их 2^5) и выбрать максимальную чувствительность.
Т.е. если мы найдем вход, чувствительность которого будет 3, но не сможем найти вход с чувствительностью 4. То результирующая чувствительность булевой функции будет равна 3.
Значит, «чувствительность» этого входа 2.Не очень понял, что в данном случае понимается под входом. Можно чуть поподробнее этот момент?
Ссылка на доказательство www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf
Для доказательства 30-летней гипотезы из области информатики хватило двух страничек