Какое будет влияние P = NP? [закрыто]

18

Я готовлюсь к тесту и не могу найти четкого ответа на вопрос: каково будет влияние доказательства того, что PTIME = NPTIME. Я проверил Википедию, и она только что упомянула, что она окажет «глубокое влияние на математику, ИИ, алгоритмы ...» и т. Д.

Кто-нибудь может дать мне ответ?

algorithms complexity latusaki
источник
Это никак не связано с разработкой программного обеспечения. Я закрыл сейчас, но спросил моды в Math.StackExchange, хотели бы они, чтобы я перенес это для вас.
maple_shaft

Ответы:

22

Первое, что приходит на ум, это то, что безопасность криптографии с открытым ключом в настоящее время зависит от неспособности перебрать математические задачи, которые есть в классе сложности NP. Если P = NP, все, что зависит от PKC (включая HTTPS, что означает всю современную всемирную инфраструктуру электронной коммерции ), должно быть переработано!

Мейсон Уилер
источник
4
Это гарантировало бы наличие алгоритмов, которые работают за полиномиальное время. Тогда будет только обратный отсчет времени до поиска этих алгоритмов, а затем, так сказать, kaboom.
Мировой инженер
7
Доказательство будет включать в себя поиск алгоритма полиномиального времени для NP-полной задачи. И когда вы найдете один полиномиальный алгоритм, вы можете использовать его для решения всех других NP-полных задач, сводя задачи к общей форме. Это означает, что доказательство для P = NP и алгоритмы, которые его используют, появятся одновременно.
Олекси
7
Конечно, постоянные факторы могут быть настолько велики, что это станет теоретической проблемой ... какое-то время.
quant_dev
17
Когда мы находим такой алгоритм, он может все еще иметь ужасно высокий постоянный коэффициент или иметь огромную степень (n ^ 10000 является полиномиальным, но для многих практических целей он намного хуже, чем небольшая экспоненциальная сложность). Конечно, это был бы предупреждающий знак для всех отойти от старых методов, как если бы мы отошли от DES до того, как было доказано, что оно решаемо, но мировая экономика не сразу рухнет. Просто подумайте о самих деньгах: все в конечном итоге знают, что на самом деле они не работают, если вы в них не верите, но глобальная торговля все еще работает нормально.
Килиан Фот
5
Мы, вероятно, прибегнем к использованию одноразовых прокладок. Amazon может отправить вам 1-гигабайтный флэш-накопитель, который будет работать с его сайтом и удерживать вас до конца вашей жизни.
Макнейл
18

Это описано в разделе «Состояние проблемы P и NP» . Определенно стоит прочитать.

Несколько важных моментов из статьи (цитируется в разделе « Что, если P = NP?» ):

  • Криптография с открытым ключом становится невозможной.
  • Поскольку все NP-полные задачи оптимизации становятся легкими, все будет намного более эффективным. Транспортировка всех форм будет составлена ​​оптимально, чтобы люди и товары перемещались быстрее и дешевле. Производители могут улучшить свое производство, чтобы увеличить скорость и создать меньше отходов.
  • Обучение становится проще благодаря использованию принципа бритвы Оккама - мы просто находим самую маленькую программу, согласующуюся с данными. Почти идеальное распознавание зрения, понимание языка и перевод и все другие учебные задачи становятся тривиальными. У нас также будут намного лучшие прогнозы погоды и землетрясений и других природных явлений.
  • P = NP также будет иметь большое значение в математике. Можно найти короткие, полностью логичные доказательства для теорем, но эти доказательства обычно чрезвычайно длинные. Но мы можем использовать принцип бритвы Оккама, чтобы распознавать и проверять математические доказательства, как это обычно пишется в журналах. Затем мы можем найти доказательства теорем, которые имеют разумную длину, скажем, до 100 страниц. Человек, который докажет, что P = NP, пойдет домой из Института Клея не с проверкой в ​​1 миллион долларов, а с семью (фактически шесть, так как гипотеза Пуанкаре кажется решенной).
vinaykola
источник
2
Я не вижу, как P = NP подразумевает, что криптография с открытым ключом невозможна. Это предполагает (но не подразумевает), что текущие реализации не так сложно сломать, как мы думали ранее. Но, как уже отмечали другие, если соответствующие константы в оптимальном алгоритме сокращения времени чрезвычайно велики, то P = NP не окажет никакого влияния на криптографию с открытым ключом.
Эмори
+1 за третий пункт - все знают, что P = NP повлияет на криптографию, но по некоторым причинам вы редко слышите о том, как это повлияет буквально на любую другую компьютерную дисциплину на планете.
BlueRaja - Дэнни Пфлюгофт
@emory: я не буду притворяться экспертом, но я понимаю, что если бы такой алгоритм был найден, даже с довольно высокой константой, нам пришлось бы полностью переосмыслить наш подход. Кроме того, кто скажет, когда алгоритм найден, мы не можем найти другой с меньшей константой? Один алгоритм разблокирует все другие NP-полные проблемы тоже. Таким образом, непосредственный эффект может быть невелик, но необходимо приложить много усилий для изменения всех существующих систем.
Винайкола
Впервые я услышал о принципе бритвы Оккама. Интересные вещи ...
UmNyobe
@vinaykola, доказывающий P = NP, не подразумевает нахождение алгоритма. Конечно, поиск алгоритма был бы самым простым (но не единственным) способом доказать P = NP, и тогда, если константы были разумными, мы могли бы поднять проблемы, которые вы подняли.
Эмори
7

У большинства проблем с NP есть «интересные» приложения из реальной жизни. P=NPбудет иметь много последствий:

  • Будет возможно решить именно те задачи оптимизации, которые сейчас аппроксимируются. Это случай проблемы коммивояжера и задачи планирования работы
  • Это нарушает некоторые меры безопасности, основанные на том, что необходимое вычислительное время огромно. Например, многие схемы и алгоритмы шифрования в криптографии основаны на факторизации числа, самый известный алгоритм имеет экспоненциальную сложность. Эти алгоритмы станут бесполезными, если найден полиномиальный алгоритм.

Суть в том, какие проблемы известны как NP-полные. Это не просто проблемы, созданные немногими учеными в отдаленном месте для развлечения друг друга. Они могут быть выражены в деловых терминах. На самом деле, некоторые собеседники предпочитают скрывать NP-полные проблемы в своих вопросах, чтобы проверить кандидатов.

UmNyobe
источник
3
Хотя целочисленная факторизация является сложной проблемой, стоит отметить, что она не является NP-полной.
dan_waterworth
4
@dan_waterworth: Не известно, является ли целочисленная факторизация NP-трудной, но известно, что она находится в NP. [Часто кажется, что люди говорят «NP-complete», когда они имеют в виду «в NP» или «NP-hard». В некотором смысле это было бы похоже на то, как если бы кто-то говорил «меньше или равно» в ситуации, когда «меньше чем» было бы более точным.]
Макнейл
5

Эти возможности описаны в «Пять мирах» Импальяццо .

Вот некоторые пункты на вынос:

  • Искусственный интеллект сможет совершить гигантский скачок. Например, при достаточном количестве «обучающих данных» самые короткие схемы для получения правильных выходных данных будут представлять собой лучший метод перевода. В частности, было бы тривиально иметь идеальное распознавание речи и языковой перевод. Если принять к сведению эту идею, если ваши данные о тренировках показывают фильмы, получившие премию Оскар, они могут создать для вас больше фильмов, удостоенных премии Оскар.

  • Алгоритмы, преподаваемые в школах, будут радикально отличаться. Вместо изучения множества различных алгоритмических методов , курсы будут сосредоточены на сведении проблем к проверке правильных ответов. Это значительно упростит программирование.

  • Экономика станет намного более эффективной. Там будет сбой, в том числе, возможно, смещение программистов. Сама практика программирования была бы больше о сборе обучающих данных, а не о написании кода. У Google были бы ресурсы, чтобы преуспеть в таком мире.

  • Поскольку криптография с открытым ключом была бы недоступна, Amazon потребуется отправить вам одноразовую панель на флэш-накопителе, чтобы сделать безопасные транзакции.

  • Математические доказательства могут быть автоматически сгенерированы и проверены.

В целом, это привнесет технологическую особенность; последствия P = NP будут далеко идущими. Кроме того, Лэнс Фортнау рассматривает этот вопрос в отдельном сообщении в блоге, которое вы должны прочитать.

Макнейл
источник
-1

Влияние доказательства P = NP будет включать возобновление интереса к поиску алгоритма сокращения. Люди также пытались бы найти некоторые нижние границы для констант, связанных с алгоритмом редукции.

Доказательство P = NP не будет таким значительным, как утверждают другие ответы, потому что оно может прийти в форме доказательства с нулевым знанием. Знание P = NP без знания алгоритма редукции будет немного отличаться от текущей ситуации.

Представьте, если кто-то доказал, что алгоритм сокращения существует, но имеет значение O (sqrt (n) + 2 ^ 4096).

Эмери
источник
1
На самом деле, существует явный алгоритм редукции, который находится в P тогда и только тогда, когда P = NP. Он заключается в переборе всех возможных программ и их параллельном запуске до тех пор, пока не будет найдено решение.
Артур Б
@ArthurB увлекательно. Предполагая, что P = NP, каков порядок алгоритма?
Эмори
Это неизвестно, но это оптимальный порядок. scholarpedia.org/article/Universal_search
Артур Б
1
@ArthurB, так что если P = NP и алгоритм сокращения O (n ^ 99999999), P = NP все еще такая большая проблема?
Эмори