Распечатать запись Распечатать запись

Самая сложная математическая задача

Иэн Стюарт рассказывает о самой сложной математической задаче для “чайников’’.

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

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

Проблема возникла в информатике. Мы обычно считаем вычисления инструментом для понимания математики, но здесь математика предстает инструментом для понимания вычислений. Компьютеры оказывают фантастическую помощь математикам. Иногда они в мгновение ока дают ответ, тогда как для его получения с помощью карандаша и бумаги потребуются объединенные усилия всех людей на планете в течение миллиона лет. Но иногда даже самый быстрый суперкомпьютер поможет не больше, чем счеты ребенка.

P/NP — математическая задача о том, как компьютер решает математические задачи. Компьютеры хороши в некоторых задачах, однако они бесполезны в других. Проблема состоит не в том, чтобы решить, что есть что. Нужно доказать, что действительно есть разница.

Компьютеры выполняют списки инструкций. “Сложить эти два числа.’’ “Начинается ли это слово с буквы Б?’’ Эти списки называются алгоритмами. Всякий раз, когда вы пользуетесь Интернетом, или летите на самолете, или используете спутниковый навигатор, или набираете документ, пользуясь текстовым процессором, вы используете алгоритм. Это может быть математический расчет, или это может быть вход в Twitter из центра Монголии. Таким образом, эта область математики на самом деле очень важна.

Для пользователей имеет значение не только результат работы алгоритма, но и как быстро машина получает этот результат. Например, существует очень простой алгоритм для написания бестселлера. Сгенерировать все возможные книги из 100000 слов, оценить их читабельность, и выбрать лучшую из них. Однако получится так много вариантов, что этот алгоритм неудачен, каким бы дорогим ни был ваш компьютер.

Алгоритмы, которые работают быстро, называются алгоритмами класса P. Эта первая буква слова “polynomial’’ (полиномиальный) — да, теперь это начинает звучать как математика — которое описывает, как быстро растет время вычислений в зависимости от увеличения объема исходных данных. Все другие алгоритмы — не-P, они работают слишком медленно, чтобы считаться полезными, за несколькими почетными исключениями. Алгоритм “написать все возможные книги’’ примерно такой же, как не-P, как вы можете видеть. Так как длина книги увеличивается, время работы растет даже быстрее, чем поголовье бессмертных кроликов, удваивающееся каждые несколько месяцев, пока эти кролики не образуют сферу, окружающую Землю и расширяющуюся со скоростью большей, чем скорость света.

“Р или не-Р, вот в чем вопрос’’, — почти так сказал Гамлет. Как правило, можно выяснить эффективность любого конкретного алгоритма. Однако все идет наперекосяк, когда мы думаем не об алгоритме, а о задаче, которую он решает. Существует ли более быстрый алгоритм решения той же задачи? Если да, то задача может быть легко решена, вы просто используете не тот метод.

Проблема принадлежит классу P, если существует эффективный алгоритм ее решения, и классу не-P, если нет. “Вот в чем вопрос’’, как сказал Гамлет все в той же речи. Что можно сделать? Вы не можете испытать все возможные алгоритмы по очереди — это как написать все возможные книги, но теперь без ограничения по количеству слов. Если вы нашли эффективный алгоритм, то задача, безусловно, класса P. Но если ваш алгоритм является неэффективным… возможно, существует другой алгоритм, лучший, который вы еще не обнаружили.

Несмотря на это, мы несомненно можем доказать, что некоторые задачи принадлежат классу не-P. “Напишите все возможные книги’’ — пример такой задачи: какой бы алгоритм вы ни использовали, он должен давать ответ, а это займет бесконечное время. Класс NP исключает такие глупые задачи, как эта. Он выделяет потенциально сложные задачи, которые имеют короткий и точный ответ. Буквы NP означают “nondeterministic polynomial’’ (“неопределенный полиномиальный’’), и N-слово означает именно то, о чем вы догадались. Любое предположение можно проверить очень быстро, но это не поможет вам решить задачу, если вам случайно не повезет.

Мой алгоритм написания бестселлера не является NP. Объем полученных книг гигантский, и чтобы убедиться в правильности результата, вы должны прочитать все и проверить, что ничего не было упущено. Ощутимо трудные задачи — это задачи, ответ в которых можно легко проверить, если вы его знаете, однако трудно найти этот ответ.

Это NP-задачи, которые не являются P-задачами. И вот вопрос на миллион долларов, P/NP задача:

NP отличается от P?

Существуют ли задачи, в которых легко проверить догадку, но практически невозможно найти правильный ответ? Большинство математиков ожидают, что ответ на этот вопрос будет “да’’, но есть и сомнения. Может быть, есть какой-то хитрый способ найти правильную догадку очень быстро, но мы слишком глупы, чтобы обнаружить его.

Подумайте о решении головоломки. Сложить части в правильное целое может быть трудно. Но если кто-то показывает вам решение головоломки, с одного взгляда можно понять, правильное оно или ошибочное. Так что я получаю мой миллион баксов? К сожалению, нет: решение головоломки на самом деле класса P — это просто тип задачи класса P, где алгоритм нахождения ответа намного медленнее алгоритма проверки его правильности.

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

Источник: http://www.publishersweekly.com/pw/by-topic/industry-news/tip-sheet/article/56050-what-s-the-hardest-math-problem-in-the-world.html

Комментариев: 7

  1. 1 вася:

    будит NP2

    [Ответить]

    Марина Reply:

    Какой NP2? Тебе нужно доказать отличается ли NP от P!

    [Ответить]

    парвкавкп Reply:

    отличается на n в любом случае

    [Ответить]

  2. 2 Пифагор-9:

    Интересная тема-стара как мир.Человеческое сознание,да и не только человеческое,в повседневной реальности вынуждено идти своим путем.Где мелкими шажками,где гиганскими шагами двигая эволюцию в трехмерном пространстве взаимодействующих состояний.Выход один-СТРАТЕГИЯ и ТАКТИКА.Наличие системы проектирования предельно оптимальных систем(СППОС),независимо от объема сочетаемых элементов- позволит,на предварительном этапе,избавиться от колллосального колличества ненужных состояний,по известному алгоритму,с минимизированной ошибкой,аналогично тому как ошибается сама Природа.Фактор времени,в динамикке событий,очень важен и не надо зацикливаться на статическом состоянии объекта,которое не мможет объять необъятнное в каруселе жизни.

    [Ответить]

  3. 3 касембай амир:

    алгоритм p решает сложные задания как и ир нет разницы

    [Ответить]

  4. 4 Математик:

    это очень лёгкая задача для меня а для вас я незнаю P/Np ЛЕГКО миллион Мой

    [Ответить]

  5. 5 Самый умный человек в мире:

    ответ да потому что np отличается тем что задачи подобные p невозможно решить а np можно анализируя происходящего этой мысли что np не равно p и ещё нет алгоритмов для вычисления np от р

    [Ответить]

Оставьте свой отзыв

Добавить изображение