В зависимости от ответа, одна из известных нерешенных проблем тысячелетия может иметь серьезные последствия в нашей жизни.
Ключевые выводы
- Задачи на премию тысячелетия - это набор из семи нерешенных математических задач, поставленных Математическим институтом Клэя, каждая из которых предусматривает приз в размере 1 миллиона долларов для тех, кто их решит.
- Одна из этих задач спрашивает, является ли P=NP. Проще говоря, это вопрос о том, действительно ли вычислительно сложные проблемы содержат скрытые, вычислительно простые решения. Однако это существенное упрощение.
- Доказательство того, что P не равно NP, станет важной вехой, и это результат, которого ожидает большинство ученых-компьютерщиков. Однако, если верно обратное, то наш мир стал бы кардинально другим, чем он есть сейчас.
В 2000 году Математический институт Клэя выложил семь нерешенных математических задач и предложил 1 миллион долларов тому, кто сможет их решить. Пока решена только одна из семи так называемых проблем тысячелетия: гипотеза Пуанкаре, которая связана с определением сфер в различных пространственных измерениях.
Для нематематиков трудно понять как природу этой задачи, так и то, почему она может стоить 1 миллион долларов. Однако другую проблему тысячелетия понять немного легче, и ее решение будет иметь серьезные последствия для функционирования нашего мира. Хотя это кажется более простым, окончательное доказательство этой проблемы так или иначе ускользало от исследователей на протяжении десятилетий. Вопрос в том, является ли P=NP.
Shutterstock
Что такое проблемы P и NP?
Проще говоря, вопрос P против NP спрашивает, входит ли набор проблем, которые можно легко решить, в набор проблем, которые можно легко проверить. Представьте, что вам нужно склеить разбитую чайную чашку. Легко убедиться, что вы преуспели - перед вами будет полная чашка чая. Но очень сложно собрать все разрозненные части и собрать их вместе. Это пример проблемы NP; сложно решить, легко проверить.
А теперь представьте, что вместо этого вам нужно посчитать, на сколько частей разбилась чашка, а не собирать ее заново. Это будет проблема P. Сравнительно легче сосчитать осколки, чем понять, как они соединяются друг с другом.
Почему эти два набора задач называются P и NP?
Компьютерным алгоритмам требуется определенное время для решения поставленной перед ними задачи. Как правило, вы можете приблизительно оценить, сколько времени займет алгоритм, используя количество элементов, которые ему необходимо обработать. Компьютерщики называют количество элементов N.
Поскольку некоторые алгоритмы более или менее эффективны, чем другие, время их выполнения может быть связано с N, N 2, N 3 и так далее. Важно, однако, то, что показатель степени является константой - это 1, или 2, и т. д. В этом случае говорят, что алгоритм завершается за полиномиальное время, или P.
К сожалению, не все задачи решаются таким образом. Решение некоторых задач может занять у алгоритма время, пропорциональное 2 N, 3 N, и так далее. В данном случае N - показатель степени, означающий, что каждый элемент, с которым приходится иметь дело алгоритму, экспоненциально увеличивает его сложность. В этом случае алгоритм может быть завершен за экспоненциальное время, или NP (что на самом деле означает недетерминированное полиномиальное время).
Разница между ними может быть огромной. Если P-алгоритм состоит из 100 элементов и время его выполнения пропорционально N 3, то он решит свою задачу примерно за 3 часа. Однако если это NP-алгоритм и время его завершения пропорционально 2 N, тогда он займет примерно 300 квинтиллионов лет.
Пользователь Flickr Ян Калаб
Почему это важно?
Еще один способ узнать, является ли P=NP, состоит в том, чтобы спросить, действительно ли каждая трудная проблема содержит простое, но скрытое решение. Являются ли эти две разновидности проблем безвозвратно отделенными друг от друга? Являются ли некоторые проблемы просто сложными по своей фундаментальной природе?
Если P действительно равно NP, то это будет иметь серьезные последствия для нашего образа жизни. Одним из основных преимуществ является то, что многие NP-задачи называются NP-полными, а это означает, что их решения можно быстро адаптировать к любой другой NP-полной задаче. Таким образом, разработка способа быстрого решения одной NP-полной задачи значительно продвинет нас к решению всех других NP-полных задач.
Каковы некоторые примеры проблем NP? Многие исследователи сосредотачиваются на одной главной проблеме. Большая часть современной криптографии опирается на коды, которые трудно взломать, но легко проверить. В качестве примера рассмотрим пароли или PIN-коды к вашим различным учетным записям. Проверить их правильность несложно, но угадывание каждой перестановки букв и цифр методом грубой силы заняло бы целую вечность. Шифрование, защищающее номер вашей кредитной карты при заказе чего-либо на Amazon, также является примером криптографии NP. Если P=NP, то взлом почти любого типа шифрования внезапно станет намного проще.
Хотя потеря любого подобия интернет-безопасности была бы катастрофой, было бы много полезных последствий, если бы P=NP. Лэнс Фортноу, ученый-компьютерщик и автор книги «Золотой билет: P, NP и поиски невозможного», резюмировал некоторые основные последствия в статье для Communications of the ACM:
Перевозки всех форм будут оптимально спланированы, чтобы перемещать людей и товары быстрее и дешевле. Производители могут улучшить свое производство, чтобы увеличить скорость и уменьшить количество отходов. И я просто царапаю поверхность. Обучение становится легким, если использовать принцип бритвы Оккама: мы просто находим наименьшую программу, согласующуюся с данными. Почти идеальное распознавание зрения, понимание языка и перевод, а также все другие учебные задачи становятся тривиальными. У нас также будут гораздо более точные прогнозы погоды, землетрясений и других природных явлений.
Вопрос о том, является ли P=NP, настолько фундаментален, что трудно выбрать лишь несколько репрезентативных задач, которые можно было бы улучшить за световые годы. Например, станет сравнительно легко предсказывать структуру белков по их аминокислотным последовательностям, что является важной вехой в разработке лекарств и биотехнологии. Другой часто упоминаемой проблемой NP является определение наиболее эффективного расположения транзисторов на компьютерном чипе, что значительно увеличивает вычислительную мощность.
На самом деле, доказательство P=NP значительно облегчило бы решение почти всех других математических задач. Фортноу также писал, что «человек, доказавший P=NP, пойдет домой из Института Клэя не с чеком на 1 миллион долларов, а с семью (на самом деле шестью, поскольку гипотеза Пуанкаре кажется решенной)».
В конечном счете, следствием доказательства того, что P=NP, будет полный переворот нынешних технологических и экономических основ общества. По всей вероятности, решение этой проблемы стало бы инновационным толчком наравне, если не больше, чем с изобретением Интернета.
Научный консенсус
К сожалению, большинство ученых-компьютерщиков не верят, что P=NP - по состоянию на 2012 год 83% ученых-компьютерщиков не верили в это утверждение. Очень трудно доказать обратное, но все неудачные попытки доказать, что P=NP, подтверждают идею о том, что эти два типа проблем в конечном счете непримиримы. Ученый из Массачусетского технологического института Скотт Аронсон написал сообщение в блоге, в котором перечислены десять причин, по которым P, скорее всего, не равно NP, а номер девять излагает аргумент, который одновременно значительно опровергает идею о том, что P=NP, и кратко описывает последствия, если бы это было правдой:
Если P=NP, то мир будет совершенно другим местом, чем мы обычно предполагаем. Не было бы особой ценности в «творческих прыжках», не было бы фундаментального разрыва между решением проблемы и признанием найденного решения. Всякий, кто мог бы оценить симфонию, был бы Моцартом; всякий, кто мог бы следовать пошаговым рассуждениям, был бы Гауссом; каждый, кто мог бы распознать хорошую инвестиционную стратегию, был бы Уорреном Баффетом.
Каждый может стать математиком, если знает, как лучше учиться …
content.jwplatform.com