Золотой билет - [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 году российский ученый Михаил Боров придумал интересную модификацию и ускорил алгоритм на порядок, однако до практического применения по-прежнему было очень и очень далеко.
Послевоенные годы знаменуются решительным наступлением нашего морского рыболовства на открытые, ранее не охваченные промыслом районы Мирового океана. Одним из таких районов стала тропическая Атлантика, прилегающая к берегам Северо-западной Африки, где советские рыбаки в 1958 году впервые подняли свои вымпелы и с успехом приступили к новому для них промыслу замечательной деликатесной рыбы сардины. Но это было не простым делом и потребовало не только напряженного труда рыбаков, но и больших исследований ученых-специалистов.
Настоящая монография посвящена изучению системы исторического образования и исторической науки в рамках сибирского научно-образовательного комплекса второй половины 1920-х – первой половины 1950-х гг. Период сталинизма в истории нашей страны характеризуется определенной дихотомией. С одной стороны, это время диктатуры коммунистической партии во всех сферах жизни советского общества, политических репрессий и идеологических кампаний. С другой стороны, именно в эти годы были заложены базовые институциональные основы развития исторического образования, исторической науки, принципов взаимоотношения исторического сообщества с государством, которые определили это развитие на десятилетия вперед, в том числе сохранившись во многих чертах и до сегодняшнего времени.
Монография посвящена проблеме самоидентификации русской интеллигенции, рассмотренной в историко-философском и историко-культурном срезах. Логически текст состоит из двух частей. В первой рассмотрено становление интеллигенции, начиная с XVIII века и по сегодняшний день, дана проблематизация важнейших тем и идей; вторая раскрывает своеобразную интеллектуальную, духовную, жизненную оппозицию Ф. М. Достоевского и Л. Н. Толстого по отношению к истории, статусу и судьбе русской интеллигенции. Оба писателя, будучи людьми диаметрально противоположных мировоззренческих взглядов, оказались “versus” интеллигентских приемов мышления, идеологии, базовых ценностей и моделей поведения.
Монография протоиерея Георгия Митрофанова, известного историка, доктора богословия, кандидата философских наук, заведующего кафедрой церковной истории Санкт-Петербургской духовной академии, написана на основе кандидатской диссертации автора «Творчество Е. Н. Трубецкого как опыт философского обоснования религиозного мировоззрения» (2008) и посвящена творчеству в области религиозной философии выдающегося отечественного мыслителя князя Евгения Николаевича Трубецкого (1863-1920). В монографии показано, что Е.
Эксперты пророчат, что следующие 50 лет будут определяться взаимоотношениями людей и технологий. Грядущие изобретения, несомненно, изменят нашу жизнь, вопрос состоит в том, до какой степени? Чего мы ждем от новых технологий и что хотим получить с их помощью? Как они изменят сферу медиа, экономику, здравоохранение, образование и нашу повседневную жизнь в целом? Ричард Уотсон призывает задуматься о современном обществе и представить, какой мир мы хотим создать в будущем. Он доступно и интересно исследует возможное влияние технологий на все сферы нашей жизни.
Что такое, в сущности, лес, откуда у людей с ним такая тесная связь? Для человека это не просто источник сырья или зеленый фитнес-центр – лес может стать местом духовных исканий, служить исцелению и просвещению. Биолог, эколог и журналист Адриане Лохнер рассматривает лес с культурно-исторической и с научной точек зрения. Вы узнаете, как устроена лесная экосистема, познакомитесь с различными типами леса, характеризующимися по составу видов деревьев и по условиям окружающей среды, а также с видами лесопользования и с некоторыми аспектами охраны лесов. «Когда видишь зеленые вершины холмов, которые волнами катятся до горизонта, вдруг охватывает оптимизм.