[Перевод] Как простая задача о голубях помогает математической теории сложности

Американцы говорят, что птица в руке стоит двух в кустах, но для компьютерных учёных две птицы в гнезде ещё лучше. А всё потому, что эти сожительствующие птицы являются героями обманчиво простой математической теоремы, называемой принципом голубятни. Её легко сформулировать в одном коротком предложении: если шесть голубей гнездятся в пяти гнёздах, то по крайней мере два из них должны жить в одном гнезде. Вот и всё. «Принцип голубятни — это теорема, которая вызывает улыбку», — говорит Кристос Пападимитриу , учёный-теоретик из Колумбийского университета. «Это прекрасная тема для разговора». Но принцип гнёзд подходит не только для птиц. Несмотря на то, что он звучит до боли просто, он стал мощным инструментом для исследователей, занимающихся центральным проектом теоретической информатики: составлением карты скрытых связей между различными задачами.

https://habr.com/ru/articles/903410/

#голуби #теория_сложности #гнезда #информатика

[Перевод] Каталитические вычисления используют заполненный жёсткий диск на полную мощность

«Очевидно» — опасное слово, даже в сценариях, которые кажутся простыми. Предположим, например, что вам нужно произвести важные вычисления. Вы выбираете между двумя почти одинаковыми компьютерами, за исключением того, что в одном из них есть дополнительный жёсткий диск, заполненный драгоценными семейными фотографиями. Естественно предположить, что эти два варианта одинаково хороши — дополнительный диск, на котором не осталось места, не поможет вам в вычислениях. «Очевидно, что это не поможет, верно?» — говорит Бруно Лофф , специалист по информатике из Лиссабонского университета. Ошибаетесь. В 2014 году Лофф и четверо других исследователей обнаружили, что добавление заполненного накопителя в принципе может сделать компьютер более мощными. Их теоретическая схема, названная каталитическими вычислениями , стала самостоятельным объектом для изучения. А недавно она помогла исследователям доказать поразительный результат (открыть новую вкладку) в смежной области компьютерной науки: Стандартный подход к решению главного открытого вопроса о роли памяти в вычислениях, скорее всего, зашёл в тупик.

https://habr.com/ru/articles/887950/

#алгоритмы #теория_сложности

[Перевод] Криптографы открыли новую основу для квантовой секретности

Допустим, вы хотите отправить личное сообщение, провести тайное голосование или надёжно подписать документ. Если вы выполняете любую из этих задач на компьютере, то для обеспечения безопасности ваших данных вы полагаетесь на шифрование. Это шифрование должно выдерживать атаки взломщиков, работающих на своих собственных компьютерах, поэтому современные методы шифрования основаны на предположениях о том, какие математические задачи компьютерам сложно решать. Но когда в 1980-х годах криптографы заложили математические основы этого подхода к информационной безопасности, несколько исследователей обнаружили, что вычислительная сложность — не единственный способ защитить секреты. Оказалось, что квантовая теория, изначально разработанная для понимания физики атомов, глубоко связана с информацией и криптографией. Исследователи нашли способ обеспечить безопасность нескольких конкретных криптографических задач непосредственно на основе законов физики. Но эти задачи были странными исключениями — для всех остальных, казалось, не существовало альтернативы классическому вычислительному подходу. К концу тысячелетия исследователи квантовой криптографии думали, что на этом история закончилась. Но всего за несколько последних лет в этой области произошёл ещё один сейсмический сдвиг.

https://habr.com/ru/articles/819519/

#теория_сложности #квантовая_криптография