Если вы можете решить эту математическую задачу, вы получите миллион долларов

1. Есть ли простой способ решить проблемы NP?
2. Типичная проблема NP: путешествие может быть очень сложным
3. P = NP или P ≠ NP?
4. Таким образом, вы получаете миллион долларов

ChristianChan / Shutterstock В 21-м веке все еще есть много вопросов и проблем, на которые исследователи еще не нашли ответов. Для прогресса нашего общества было бы чрезвычайно важно решить их. Некоторые проблемы даже настолько неотложны, что могут сделать ум, который находит их решение очень богатым.

Одна из этих загадок - проблема P-NP. Математический институт глины объявил это вызовом тысячелетия в 2000 году и тот, кто может ее решить, обещал приз в размере одного миллиона долларов (896 000 евро). Однако до сих пор головоломка все еще не решена, так как Сайт института то есть. Если хотите, вы все равно можете попробовать. Но мы должны предупредить вас, проблема довольно хорошая.

Есть ли простой способ решить проблемы NP?

Задача P-NP заключается в поиске алгоритмов, которые компьютерная программа может использовать для решения конкретной математической задачи. Задачи делятся на классы P и NP. Хотя относительно легко проверить, является ли найденное решение правильным, время и усилия, необходимые для нахождения правильного ответа, сильно различаются: проблемы класса P могут быть быстро решены с помощью алгоритмов, в то время как проблемы класса NP могут быть решены только медленно. Так что довольно неэффективными алгоритмами можно решить. Таким образом, Институт математики Клея определяет задачи P как простые для решения, а задачи NP как простые для проверки.

Большой вопрос сейчас заключается в том, нет ли быстрого решения проблем НП, которое еще не найдено. Или, другими словами: Есть ли какие-либо вопросы, решение которых может быть быстро проверено компьютером, но которые, в то же время, могут быть решены только в непропорционально долгое время любыми средствами?

Типичная проблема NP: путешествие может быть очень сложным

Классический пример P-задачи: несколько натуральных чисел должны быть отсортированы по размеру. Эту проблему довольно легко решить, пройдя все числа, выбрав наименьшее, затем снова пройдя все оставшиеся числа, выбрав наименьшее и т. Д. Процедура всегда одна и та же, она занимает немного больше времени, чем больше чисел нужно отсортировать.

Проблемы с NP более сложны. Популярным примером проблемы NP является способ коммивояжера, который должен посетить 100 городов в кратчайшие сроки, не будучи в одном и том же городе дважды. В конце концов, однако, он должен вернуться к своей отправной точке. Чтобы объяснить эту проблему немного яснее, мы выбрали более короткую, но не менее сложную поездку с четырьмя городами:

Энди Кирш / Business Insider

Города расположены в точках A, B, C и D, их расстояние друг от друга обозначено синими цифрами. Все это не логически верно масштабировать здесь.

Например, чтобы добраться до всех четырех городов, коммивояжёр мог бы проехать сначала из А в В, затем из В в D, затем обратно в С, а затем обратно в начальную точку А. Если он выберет этот маршрут, ему придется пройти следующее расстояние. : 1 + 6 + 3 + 5 = 15

Энди Кирш / Business Insider

Но это самый короткий путь? Чтобы выяснить это, нам нужно будет проверить все возможные маршруты. Это все еще относительно легко для четырех городов (самый короткий маршрут - ABCDA или ADCBA), но для 100 городов это очень сложно и навсегда останавливает компьютер. Даже с 30 городами уже существует около девяти квинтилонов (девять с 30 нулями) возможных путей. Если бы компьютер мог проверять один триллион путей в секунду, он потратил бы здесь 280 миллиардов лет ...

Но, в конце концов, легко найти возможное решение - в приведенном выше случае нам просто нужно найти маршрут, который короче, но не обязательно должен быть кратчайшим, но очень сложным или Трудно найти правильное решение, это проблема NP.

P = NP или P ≠ NP?

Но вернемся к вопросу, на который необходимо ответить: существуют ли проблемы, решение которых может быть быстро проверено компьютером, но которые в то же время могут быть решены только непропорциональным количеством времени?

Это также можно сформулировать следующим образом: P = NP или P ≠ NP?

Напомним, что проблемы P были определены как легко решаемые, а проблемы NP - легко проверяемыми. Все проблемы P включены в класс проблем NP: любая проблема, которая может быть легко решена компьютером, также имеет потенциальное решение, которое может быть быстро рассмотрено им. Но верно ли обратное, т. Е. Включены ли все проблемы NP в класс P-задач, неизвестно: еще не известно, могут ли проблемы, чье возможное решение можно быстро проверить с помощью компьютера, также с помощью эффективного алгоритма может быть быстро решена с помощью компьютера.

Таким образом, вы получаете миллион долларов

Большинство математиков считают, что P ≠ NP. Но это не доказано математически. Чтобы очистить призовой фонд в 1 миллион долларов, вам придется столкнуться с отсутствием доказательств того, что существует хотя бы одна проблема NP, которая не может быть решена быстрым алгоритмом и что такой алгоритм не может быть найден теоретически. В качестве альтернативы, вы также можете доказать, что P = NP. Даже тогда вы получите призовой фонд. Взамен вам нужно будет найти упомянутый эффективный алгоритм и доказать, что все проблемы NP могут быть решены с его помощью.

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

Похожие

Комментарии