Рубрика «колмогоровская сложность»

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

В 1868 году математик Чарльз Доджсон (более известный как Льюис Кэрролл) заявил, что схема шифрования под названием «шифр Виженера» является «невзламываемой». У него не было доказательств, однако имелись убедительные подтверждения этой веры: математики безуспешно пытались его взломать более трёх сотен лет.

Была лишь одна небольшая проблема: на самом деле, пятью годами ранее её взломал немецкий пехотный офицер Фридрих Касиски, описав решение в книге, привлёкшей на тот момент мало внимания.

Криптографы играли в эти «кошки-мышки», создавая и взламывая шифры, ещё с тех пор, как люди впервые начали передавать секретную информацию. «Тысячи лет люди пытались найти ответ на вопрос: сможем ли мы разорвать этот круг?», — рассказывает криптограф Рафаэль Пасс из Cornell Tech и Корнеллского университета.

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

Парадоксы о сжатии данных - 1 Задача сжатия данных в своей простейшей форме может относиться к числам и их обозначениям. Числа можно обозначать числительными («одиннадцать» для числа 11), математическими выражениями («два в двадцатой» для 1048576), строковыми выражениями («пять девяток» для 99999), именами собственными («число зверя» для 666, «год смерти Тьюринга» для 1954), или произвольными их комбинациями. Годится любое обозначение, по которому собеседник сможет однозначно определить, о каком числе речь. Очевидно, что сообщить собеседнику «факториал восьми» эффективнее, чем эквивалентное обозначение «сорок тысяч триста двадцать». Здесь возникает логичный вопрос: какое обозначение для заданного числа самое короткое?

Философ Бертран Рассел в 1908 опубликовал «парадокс Берри», который затрагивает вопрос обозначений чисел с противоположной стороны: какое самое маленькое число, для обозначения которого недостаточно восьмидесяти букв?
Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 3480 чисел. Значит, некое число, не большее чем 3480, обозначить таким образом невозможно.

Значит, этому числу будет соответствовать обозначение «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв», в котором всего 78 букв! С одной стороны, это число обязано существовать; с другой, если это число существует, то его обозначение ему не соответствует. Парадокс!Читать полностью »

Что математика может рассказать нам о поиске порядка в хаосе жизни

Колмогоровская сложность и наши поиски смысла - 1

Была ли встреча с самым дорогим вам человеком случайной, или виной тому была какая-то скрытая причина? А что насчёт странного вчерашнего сна – это были только случайные метания синапсов мозга, или он раскрыл что-то глубокое по поводу вашего подсознания? Возможно, сон пытался рассказать вам что-то о вашем будущем. Возможно, что и нет. Имеет ли тот факт, что ваш близкий родственник заболел опасной разновидностью рака, какой-то глубокий смысл, или же это просто последствия случайных мутаций ДНК?

В нашей жизни мы часто задумываемся над закономерностями происходящих вокруг нас событий. Мы задаёмся вопросом, случайны ли наши жизни, или у них есть какой-то смысл, уникально истинный и глубокий. Я, как математик, часто обращаюсь к числам и теоремам за идеями по поводу подобных вопросов. И так получилось, что я кое-что узнал о поиске смысла в закономерностях жизни благодаря одной из самых глубоких теорем математической логики. Эта теорема, проще говоря, демонстрирует, что в принципе невозможно узнать, является ли объяснение закономерности наиболее глубоким или интересным из всех объяснений. Точно так же, как в жизни, поиск смысла в математике ничем не ограничен.
Читать полностью »

В поисках лучшего бенчмарка для нейросетей - 1Бывало ли у вас так — быстро запомнил что-то, а через некоторое время “прозрел”, почему оно именно так? Например, можно просто запомнить, что антиградиент — это направление быстрейшего спуска. А можно представить себе геометрический смысл частной производной, провести в уме плоскости/касательные и понять, что антиградиент и правда обязан показывать направление спуска.

Как отличить, нейросеть поняла или просто запомнила? И какой бенчмарк позволит численно это померить?
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js