Золотой билет - [5]
Какова предыстория проблемы равенства P и NP? На самом деле здесь не одна история, а целых две. События разворачивались в те времена, когда Холодная война разделила мир на противоборствующие лагеря; понятие эффективных вычислений и связанные с ним вопросы независимо разрабатывались по разные стороны «железного занавеса». В итоге оба пути сошлись в одной точке, и эта точка получила имя «P против NP».
С какой стороны зайти, чтобы вывести неравенство P ≠ NP? Курт Гёдель показал, что не у всех математических проблем имеется решение; возможно, аналогичным образом удастся доказать тот факт, что не для всех поисковых задач существует быстрый алгоритм. Еще вариант – попытаться разделить вычислительный процесс на более мелкие части, чтобы сложность исходной задачи было легче оценить. Некоторую надежду дает также алгебраическая геометрия – молодой и абсолютно абстрактный раздел математики. Впрочем, до решения проблемы мы в любом случае дойдем еще очень не скоро.
Какая нам польза от того, что P и NP не равны? Доказав неравенство, мы будем уверены в сохранности наших персональных данных и сможем создавать псевдослучайные числа, неотличимые от настоящих.
Изменят ли ситуацию компьютеры будущего, основанные на принципах квантовой механики? Снимут ли они проблему «P против NP»? Маловероятно, хотя с их помощью мы сможем решать некоторые недоступные современным машинам задачи, например, раскладывать большие числа на множители. Кстати, квантовая механика даст нам абсолютно стойкие шифры вне зависимости от того, равны классы P и NP или не равны.
Так что же дальше? Похоже, самые большие трудности ждут нас впереди. Как организовать совместную работу нескольких компьютеров над одной задачей? Как проанализировать колоссальные объемы данных, которые мы создаем изо дня в день? Каким станет мир, когда интернет людей превратится в интернет вещей? Чем больше перед нами возникает подобных задач, тем большую значимость приобретает вопрос о равенстве P и NP.
Решение задачи о разбиении
Упомянутые ранее тридцать восемь чисел
14175, 15055, 16616, 17495, 18072, 19390, 19731, 22161, 23320, 23717, 26343, 28725, 29127, 32257, 40020, 41867, 43155, 46298, 56734, 57176, 58306, 61848, 65825, 66042, 68634, 69189, 72936, 74287, 74537, 81942, 82027, 82623, 82802, 82988, 90467, 97042, 97507, 99564
можно разбить на две равные группы следующим образом:
15055, 16616, 19390, 22161, 26343, 40020, 41867, 43155, 46298, 57176, 58306, 65825, 66042, 69189, 74537, 81942, 82623, 82988, 90467
и 14175, 17495, 18072, 19731, 23320, 23717, 28725, 29127, 32257, 56734, 61848, 68634, 72936, 74287, 82027, 82802, 97042, 97507, 99564.
Числа каждой группы дают в сумме ровно 1000000.
Глава 2. Совершенный мир
Представьте, что вас просят написать статью обо всех переменах, вызванных развитием интернета за последние двадцать лет. Вы ведь упомянете о компактном устройстве, которое лежит у вас в кармане и мгновенно предоставляет доступ к любой открытой информации? И о новом типе общения, сложившемся в социальных сетях? И о том, как трансформировалось кино и музыка? О нововведениях в работе издательств и новостных агентств? Изменений слишком много, и в одну статью их явно не вместить. А теперь вообразите, что сейчас начало девяностых и вы пишете статью, когда все это еще только предстоит…
Равенство P и NP будет означать, что у нас имеется универсальный эффективный алгоритм для всех NP-задач. Мир изменится настолько сильно, что развитие интернета превратится во второстепенный исторический факт. Описать сейчас подробно эти изменения или хотя бы предсказать основные последствия от внедрения новых технологий не представляется возможным.
Совершенный мир, в котором P = NP, вряд ли когда-нибудь станет реальностью. Однако заглянуть в него одним глазком мы все-таки можем. Представим наше общество через несколько лет после появления универсального эффективного алгоритма; перенесемся в далекий 2026-й и посмотрим для начала, как этот мир развивался.
Урбанский алгоритм
В 2016 году чешский математик Милена Павел послала по электронной почте письмо. Во вложении было описание универсального эффективного алгоритма для решения NP-задач. После долгих и тщательных проверок научное сообщество пришло к единому мнению: алгоритм работает, и проблема равенства P и NP наконец решена. Свою работу Милена скромно назвала «Об открытой проблеме Стивена Кука», а вот New York Times выпустила статью с громким и предельно кратким заголовком: «P = NP».
В 2018 году Милена Павел была удостоена Филдсовской премии. Эту престижную математическую награду впервые вручили женщине. Годом позже Математический институт Клэя выписал на имя Милены чек в один миллион долларов. Григорий Перельман был первым, кто решил одну из задач тысячелетия; Милена стала второй и в отличие от Перельмана свой приз забрала. Часть денег (точные цифры не раскрываются) она пожертвовала на учреждение стипендий в своем родном университете в Праге.
В теории алгоритм Милены стал настоящим прорывом; в реальности же он работал слишком долго и потому оказался совершенно неприменим. В 2017 году российский ученый Михаил Боров придумал интересную модификацию и ускорил алгоритм на порядок, однако до практического применения по-прежнему было очень и очень далеко.
Перед вами первое подробное исследование норм жизни населения России после Второй мировой войны. Рассматриваются условия жизни в городе в период сталинского режима. Основное внимание уделяется таким ключевым вопросам, как санитария, доступ к безопасному водоснабжению, личная гигиена и эпидемический контроль, рацион, питание и детская смертность. Автор сравнивает условия жизни в пяти ключевых промышленных районах и показывает, что СССР отставал от существующих на тот момент норм в западно-европейских странах на 30-50 лет.
В книге воспоминаний заслуженного деятеля науки РФ, почетного профессора СПбГУ Л. И. Селезнева рассказывается о его довоенном и блокадном детстве, первой любви, дипломатической работе и службе в университете. За кратким повествованием, в котором отражены наиболее яркие страницы личной жизни, ощутимо дыхание целой страны, ее забот при Сталине, Хрущеве, Брежневе… Книга адресована широкому кругу читателей.
Содержание антологии составляют переводы автобиографических текстов, снабженные комментариями об их авторах. Некоторые из этих авторов хорошо известны читателям (Аврелий Августин, Мишель Монтень, Жан-Жак Руссо), но с большинством из них читатели встретятся впервые. Книга включает также введение, анализирующее «автобиографический поворот» в истории детства, вводные статьи к каждой из частей, рассматривающие особенности рассказов о детстве в разные эпохи, и краткое заключение, в котором отмечается появление принципиально новых представлений о детстве в начале XIX века.
Монография впервые в отечественной и зарубежной историографии представляет в системном и обобщенном виде историю изучения восточных языков в русской императорской армии. В работе на основе широкого круга архивных документов, многие из которых впервые вводятся в научный оборот, рассматриваются вопросы эволюции системы военно-востоковедного образования в России, реконструируется история военно-учебных заведений лингвистического профиля, их учебная и научная деятельность. Значительное место в работе отводится деятельности выпускников военно-востоковедных учебных заведений, их вкладу в развитие в России общего и военного востоковедения.
Как цикады выживают при температуре до +46 °С? Знают ли колибри, пускаясь в путь через воды Мексиканского залива, что им предстоит провести в полете без посадки около 17 часов? Почему ветви некоторых деревьев перестают удлиняться к середине июня, хотя впереди еще почти три месяца лета, но лозы и побеги на пнях продолжают интенсивно расти? Известный американский натуралист Бернд Хайнрих описывает сложные механизмы взаимодействия животных и растений с окружающей средой и различные стратегии их поведения в летний период.
Немногие культуры древности вызывают столько же интереса, как культура викингов. Всего за три столетия, примерно с 750 по 1050 год, народы Скандинавии преобразили северный мир, и последствия этого ощущаются до сих пор. Викинги изменили политическую и культурную карту Европы, придали новую форму торговле, экономике, поселениям и конфликтам, распространив их от Восточного побережья Америки до азиатских степей. Кроме агрессии, набегов и грабежей скандинавы приносили землям, которые открывали, и народам, с которыми сталкивались, новые идеи, технологии, убеждения и обычаи.