Это мой первый вопрос на этом сайте. Я учусь в магистратуре по теории вычислений. Как бы вы объяснили проблему P = NP 10-летнему ребенку и почему он получил такое денежное вознаграждение?
Твой дубль?
Я обновлю вопрос, когда моя голова прояснит это.
cc.complexity-theory
soft-question
teaching
p-vs-np
Mohsin Hijazee
источник
источник
Ответы:
Я использую эти 3 слайда, чтобы показать, почему так сложно (невозможно?) Придумать быстрый алгоритм для задачи NP:
источник
В этой беседе Скотт Ааронсон обращается к вопросу.
TEDxCaltech - Скотт Ааронсон - Физика в 21 веке: трудится в тени Фейнмана
Предупреждение: Пожалуйста, НЕ показывайте этот разговор напрямую своей бабушке / 10-летнему. Почему? смотри, и ты узнаешь. ;-)
РЕДАКТИРОВАТЬ:
Дайте ребенку 8 королев головоломки, чтобы решить. Также дайте ему ограничение по времени.
Если он «находит» решение, то он умный ребенок, и вы можете сразу начать учить его CS. :)
Иначе вы покажете ему решение и попросите его «проверить», если оно правильное.
Что вы делаете в CS, так это либо решаете проблему, либо доказываете, что никто не может.
источник
Одна из главных вещей, для которых люди используют компьютеры, - это поиск. Такие программы, как Google, даже называют «поисковыми системами», и они используются миллионы раз в день. Компьютер недавно избил людей в «Опасности», потому что он был способен искать тонны данных, очень быстро.
Но некоторые вещи трудно найти даже на компьютерах. Звучит странно, не правда ли? Одним из примеров является обратное умножение. Конечно, если я скажу "Что 5 раз 3?" Вы можете сказать «15» в наносекунду, оуууу! Но каков ответ на вопрос: «Какие два числа, умноженные вместе, равны 21?» (Ждите ответа, 7 х 3). Верно! Теперь, что два числа, умноженные вместе равны 23? (Ждите ответа или разочарования.)
Единственные два числа, умноженные вместе, которые равны 23, являются 1 и 23 непосредственно. Это заставило задуматься, не так ли? И 23 это небольшое число. Подумайте, если бы число было длиной в сотни цифр. И дело в том, что лучшие программы в мире не могут обратить умножение намного лучше, чем мог бы попытаться семилетний ребенок, просто протестировав одно число, затем следующее, а затем следующее. Компьютеры могут делать это быстрее , но мы не знаем, как заставить компьютер делать это умнее . Люди получают докторскую степень в этом деле, и они знают, как заставить компьютеры делать обратное умножение немного умнее.
Так что, возможно, нет более разумного пути. Но, возможно, есть, и мы просто еще не нашли его. Это вкратце проблема P / NP: если я сразу узнаю ответ - 1 раз 23 - 23, да - это мне поможет? быстрее найти ответ? Люди думают, что так важно, что человек, который придумывает ответ, да или нет, выиграет миллион долларов.
источник
Я думаю, что проблема P против NP может быть очень мягко объяснена с точки зрения судоку. Я предполагаю, что этот десятилетний ребенок знаком с судоку. Я попытаюсь отдать предпочтение простоте, а не строгости в моем объяснении.
Вот моя попытка объяснить P = NP гипотетическому десятилетнему ребенку:
Как видите, я немного буквально воспринял «объясни это десятилетней». :)
Надеюсь это поможет.
источник
Вот как я объяснил это моей маме, надеюсь, она вам послужит :)
Есть проблемы, для которых легко найти решение (P, но меньше их называют «легко решаемыми»), проблемы, для которых легко проверить, является ли данное решение правильным (NP, но давайте назовем их «легко проверяемыми») ) и проблемы, которые нельзя ни легко решить, ни легко проверить. Для простоты предположим, что «Легко» формально определено, и что каждая проблема имеет уникальное решение.
Теперь люди смогли доказать (используя математику) интересные отношения между этими двумя понятиями «легко разрешимый» и «легко проверяемый», так что некоторые проблемы не легко решаемы, а некоторые другие не легко проверяемы. Основной пример такого результата состоит в том, что легко решаемая задача также легко проверяется: просто найдите ее решение и сравните ее с данным решением.
Достаточно заманчиво, для многих практических задач (таких как решение, есть ли возможное назначение студентов профессорам и классным комнатам, когда есть очень маленький запас), не известно, есть ли "легкий" способ решить это, но известно, как легко проверить, является ли решение правильным или нет. Люди много пытались и потерпели неудачу, затем попытались доказать, что это было невозможно, а также потерпели неудачу: они просто не знают. Некоторые думают, что все проблемы, которые легко проверить, легко решаемы (мы просто должны больше думать об этом), некоторые думают наоборот, что мы не должны тратить свое время, пытаясь найти простые решения этих проблем.
Мы выяснили, как показать связь между проблемами (например, если вы знаете, как ходить в школу, вы знаете, как идти в пекарню, которая находится прямо напротив) и легко проверяемыми проблемами, которые связаны со всеми другими легко проверяемыми проблемами ( NP-complete, но давайте назовем их «ключевыми проблемами»), так что если кто-то когда-нибудь покажет, что одна из ключевых проблем легко решаема, то все проблемы, которые легко проверяемы, также легко разрешимы (то есть P = NP). С другой стороны, если кто-то показывает, что одна из ключевых проблем не может быть легко решаема, то ни одна из других проблем также не может быть легко решаема (т. Е. P <> NP).
Таким образом, этот вопрос является заманчивым и относительно важным на практике (хотя некоторые утверждают, что нам следует сосредоточиться на альтернативных определениях «простого»), и люди вкладывают в дебаты довольно много денег и времени.
источник
Майкл Сипсер очень интуитивно объясняет проблему P против NP в этом видео .
источник
Я немного скептически отношусь к возможности объяснить эту проблему 10-летнему, или даже непрофессионалу, без искажения ключевых понятий.
Все объяснения, сформулированные в терминах «легкость» и «сложность» нахождения против проверочных решений, предполагают тезис Кобхэма, который в общем случае является ложным и в лучшем случае может считаться чуть более чем практическим правилом.
источник
выигрышные стратегии для различных классических настольных игр, таких как линейный или (в последнее время) видеоигры, доказали свою готовность к завершению, и это отличный способ представить / описать некоторые основные теории для новичков.
линкор как NP полное решение проблемы Merlijn Sevenster ICGA журнал сентябрь 2004
тральщик это NP полный FAQ на от математика RW Kaye. Весной 2000 года выпуск Математического интеллекта (том 22 № 2, страницы 9-15)
Игры - тяжелая работа, но кто-то должен это делать!архив Джованни Вильетты. анализирует вычислительную сложность Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Принца Персии, Lemmings, Doom, Puzzle Bobble 3 и Starcraft.
Pacman - трудная экстремальная техническая статья на бумаге выше
источник
И вот мой взгляд на проблему.
Kido!
Вы знаете, мы сталкиваемся со многими проблемами в нашей жизни. Вы можете сказать, проблемы. Некоторые трудны, некоторые легче. Например, вам часто нужно добавить два числа. А вчера вечером мы были на шахматной доске, и нам пришлось побеждать нашего соседа. Ну, добавление двух чисел - это простая и прямая проблема с ограниченными шагами. Такие проблемы называются проблемами класса P, потому что есть много проблем, которые довольно просты с дискретными шагами, которые нужно повторять снова и снова, чтобы получить решение.
С другой стороны, вчера вечером в нашей игре сундуков, какова была бы лучшая стратегия, чтобы выиграть игру? Мы могли бы переместить первую пешку на один шаг или вторую пешку на один шаг, или мы могли бы переместить вторую пешку на два шага и первую пешку на один шаг, чтобы вы увидели множество возможностей. Но есть ли способ для нас или получателя, который дает нам полные упорядоченные наборы ходов, которые дают лучший и мат? Таким образом, вы видите, что это довольно сложно, потому что существует так много возможностей, каждый шаг. Миллиарды и миллиарды, как говорит Карл Саган.
Но, дорогая, что, если я расскажу вам все позиции на доске и спросить вас - это мат? Конечно, в течение нескольких экзаменов вы сможете быстро определить, есть ли какие-либо законные ходы, оставленные королю.
Поэтому такие проблемы, которые трудно решить, но если их решение легко проверить в несколько простых шагов, они называются проблемами NP.
Теперь вы спросите, что означает P = NP? На самом деле этот вопрос означает, что есть ли способ найти более простое решение для нахождения наилучшей стратегии или упорядоченного списка ходов для игры в шахматы, не используя все миллиарды возможностей, как мы делаем для простого дополнения? Этот простой вопрос еще не получен. У нас нет ни доказательств его правды, ни отвержения, но если мы это сделаем, это будет прорыв. Если это окажется правдой, наша цивилизация может решить очень сложные проблемы, превратив их в задачи класса P. Люди смогут за несколько секунд взламывать пароли, сообщения будут расшифровываться и многое другое, поэтому эта проблема считается одной из самых важных проблем тысячелетия.
источник