Объясните P = NP проблемы до 10 лет

54

Это мой первый вопрос на этом сайте. Я учусь в магистратуре по теории вычислений. Как бы вы объяснили проблему P = NP 10-летнему ребенку и почему он получил такое денежное вознаграждение?

Твой дубль?

Я обновлю вопрос, когда моя голова прояснит это.

Mohsin Hijazee
источник
11
Я склоняюсь к тому, чтобы закрыть это, поскольку не являюсь научным уровнем теоретической информатики.
Дейв Кларк
11
@ Дэйв: На это должны ответить исследователи, так что, может быть, уместно спросить его там, где идут исследователи?
Джереми
11
Я думаю, что это разумно. Есть известная статья под названием «Как объяснить протоколы с нулевым знанием для ваших детей», которая, я думаю, будет рассматриваться на исследовательском уровне. Это правда, что может быть трудно выбрать «лучший ответ», но это часто бывает с мягкими вопросами. Кроме того, этот вопрос может оказаться хорошей рекламой для сайта, если появятся достаточно интересные ответы ... многие люди могут дать ссылку на ответ, приведенный здесь, когда их спросят о объяснении P против NP.
Филипп Уайт
7
но это действительно должно быть CW.
Суреш Венкат
5
Я спросил мотивацию, потому что формулировка вопроса создала у меня впечатление, что вас не очень интересуют ответы на ваш собственный вопрос (это выглядело как способ начать разговор, а не как реальный вопрос), а не потому, что вопрос тупой , Согласно вашему ответу, вы, кажется, задавали этот вопрос ради того, чтобы задать вопрос, и поэтому я не заинтересован в том, чтобы ответить на него, потому что он вам не поможет. У нас другая культура от переполнения стека, но сейчас это не актуально.
Tsuyoshi Ito

Ответы:

33

Я использую эти 3 слайда, чтобы показать, почему так сложно (невозможно?) Придумать быстрый алгоритм для задачи NP:

Бин упаковка Бин упаковочный НП комплект 1 Бункер упаковочный НП комплект 2

Джеффри Де Смет
источник
Очень легко понять.
до
4
Я думаю, что «нелегкий путь» нужно расширять, включая масштабирование, поскольку количество блоков увеличивается
Ян Рингроз
3
Очень хороший пример, но разве это не называется проблемой упаковки прямоугольников в литературе?
Мухаммед Аль-Туркистани
1
@ user54609 NP-complete не означает, что мы можем убедиться, что упаковка является оптимальной за полиномиальное время. NP-полная означает, что мы можем проверить, что решение выполнимо за полиномиальное время (и не всегда найти его за полиномиальное время (если P == NP)).
Джеффри Де Смет
1
О, так что проблема решения "есть ли возможное решение". Понимаю.
Итиша
21

В этой беседе Скотт Ааронсон обращается к вопросу.

TEDxCaltech - Скотт Ааронсон - Физика в 21 веке: трудится в тени Фейнмана

Предупреждение: Пожалуйста, НЕ показывайте этот разговор напрямую своей бабушке / 10-летнему. Почему? смотри, и ты узнаешь. ;-)

РЕДАКТИРОВАТЬ:
Дайте ребенку 8 королев головоломки, чтобы решить. Также дайте ему ограничение по времени.

Если он «находит» решение, то он умный ребенок, и вы можете сразу начать учить его CS. :)
Иначе вы покажете ему решение и попросите его «проверить», если оно правильное.

ClassCheckFindExamplePEasyEasyMultiply numbersNPEasyHard8 queens

P

NP

Если мы можем так легко «проверить» решение, то почему мы не можем «легко» найти его?

Что вы делаете в CS, так это либо решаете проблему, либо доказываете, что никто не может.

ClassCheckFindPEasyEasyNPEasyEasy
P=NP

NPPNP

Pratik Deoghare
источник
3
Возможно, вы могли бы обобщить суть объяснения Скотта.
Дэйв Кларк
2
Мне всегда было любопытно, что же такое суета P = NP, теперь я делаю!
Ли Ковальковски
Поскольку P ∈ NP, возможно, поясните, что вы говорите о не-P части NP здесь.
Дэвид
+1 Много отличных ответов в этой теме, но это единственный, который даже пытается определить, что вообще значат P и NP!
Марк Э. Хаас
«Если мы можем« проверить »решение так легко, то почему мы не можем« найти »его легко?» --- на этот вопрос еще нет ответа! В противном случае, это лучший ответ для меня.
19

Одна из главных вещей, для которых люди используют компьютеры, - это поиск. Такие программы, как Google, даже называют «поисковыми системами», и они используются миллионы раз в день. Компьютер недавно избил людей в «Опасности», потому что он был способен искать тонны данных, очень быстро.

Но некоторые вещи трудно найти даже на компьютерах. Звучит странно, не правда ли? Одним из примеров является обратное умножение. Конечно, если я скажу "Что 5 раз 3?" Вы можете сказать «15» в наносекунду, оуууу! Но каков ответ на вопрос: «Какие два числа, умноженные вместе, равны 21?» (Ждите ответа, 7 х 3). Верно! Теперь, что два числа, умноженные вместе равны 23? (Ждите ответа или разочарования.)

Единственные два числа, умноженные вместе, которые равны 23, являются 1 и 23 непосредственно. Это заставило задуматься, не так ли? И 23 это небольшое число. Подумайте, если бы число было длиной в сотни цифр. И дело в том, что лучшие программы в мире не могут обратить умножение намного лучше, чем мог бы попытаться семилетний ребенок, просто протестировав одно число, затем следующее, а затем следующее. Компьютеры могут делать это быстрее , но мы не знаем, как заставить компьютер делать это умнее . Люди получают докторскую степень в этом деле, и они знают, как заставить компьютеры делать обратное умножение немного умнее.

Так что, возможно, нет более разумного пути. Но, возможно, есть, и мы просто еще не нашли его. Это вкратце проблема P / NP: если я сразу узнаю ответ - 1 раз 23 - 23, да - это мне поможет? быстрее найти ответ? Люди думают, что так важно, что человек, который придумывает ответ, да или нет, выиграет миллион долларов.

Аарон Стерлинг
источник
4
Хороший. Вероятно, не имеет значения, что факторинг, кстати, плохой пример (или это?).
Рафаэль
4
Факторинг был примером, который Майк Сипсер использовал в своем видео «Объясни P / NP для публики» для Института математики Клея. Я полагаю, если это достаточно хорошо для него .....
Аарон Стерлинг
3
Проблему подмножества сумм можно объяснить ученикам, которые еще не изучали умножение!
Тегири Ненаши
16

Я думаю, что проблема P против NP может быть очень мягко объяснена с точки зрения судоку. Я предполагаю, что этот десятилетний ребенок знаком с судоку. Я попытаюсь отдать предпочтение простоте, а не строгости в моем объяснении.

Вот моя попытка объяснить P = NP гипотетическому десятилетнему ребенку:

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

Вопрос P = NP спрашивает, существует ли очень быстрый пошаговый процесс для решения головоломки Судоку, который еще не закончен. Пошаговый процесс должен быть настолько ясным и понятным, что даже компьютер может его понять и использовать для автоматического и быстрого решения головоломок Судоку. Если есть такой быстрый пошаговый процесс, то математики называют это «алгоритмом полиномиального времени» (я объясню, что это значит, когда вы станете старше).

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

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

Большинство умных математиков считают, что P = NP не соответствует действительности. Другими словами, большинство людей думают, что никто никогда не сможет быстро решить действительно сложные головоломки Судоку. Тем не менее, никто никогда не мог доказать, что P не равен NP раньше, поэтому организация, называемая Институтом математики Клея, предлагает приз в размере одного миллиона долларов за первое доказательство истинности P = NP или за первое доказательство того, что это ложь.

Как видите, я немного буквально воспринял «объясни это десятилетней». :)

Надеюсь это поможет.

Филип Уайт
источник
Очень хорошая попытка, хотя я не знаю, узнает ли 10-летний подросток, что такое загадка судоку.
Chazisop
2
@chazisop По опыту могу сказать, что базовые версии головоломок судоку (т.е. в сетке 4х4) были предоставлены детям в 3 и 4 классах в качестве упражнений, так что это не является необоснованным предположением.
Боб Фрейзер
n1000
1
@ Mohsin, пожалуйста. @ Рафаэль, я не думаю, что мне нужно бросать P и NP; десятилетний ребенок может просто принять мое определение проблемы, не зная, что означают P и NP, и я не уверен, как я мог бы объяснить проблему, не обращаясь к ней :). Кроме того, я сказал, что предпочитаю ясность, а не полную точность ... поэтому я не думаю, что несправедливо использовать «очень быстрое» и «полиномиальное время» взаимозаменяемо.
Филипп Уайт
Я хочу сказать, что использование «быстрого» не создает ясности. Предполагая, что P = NP, возможно, «единственная» проблема состоит в том, что мы ищем «быстрые» алгоритмы для задач, которые не могут быть решены «быстро», но только полиномиально с высокими степенями.
Рафаэль
8

Вот как я объяснил это моей маме, надеюсь, она вам послужит :)

Есть проблемы, для которых легко найти решение (P, но меньше их называют «легко решаемыми»), проблемы, для которых легко проверить, является ли данное решение правильным (NP, но давайте назовем их «легко проверяемыми») ) и проблемы, которые нельзя ни легко решить, ни легко проверить. Для простоты предположим, что «Легко» формально определено, и что каждая проблема имеет уникальное решение.

Теперь люди смогли доказать (используя математику) интересные отношения между этими двумя понятиями «легко разрешимый» и «легко проверяемый», так что некоторые проблемы не легко решаемы, а некоторые другие не легко проверяемы. Основной пример такого результата состоит в том, что легко решаемая задача также легко проверяется: просто найдите ее решение и сравните ее с данным решением.

Достаточно заманчиво, для многих практических задач (таких как решение, есть ли возможное назначение студентов профессорам и классным комнатам, когда есть очень маленький запас), не известно, есть ли "легкий" способ решить это, но известно, как легко проверить, является ли решение правильным или нет. Люди много пытались и потерпели неудачу, затем попытались доказать, что это было невозможно, а также потерпели неудачу: они просто не знают. Некоторые думают, что все проблемы, которые легко проверить, легко решаемы (мы просто должны больше думать об этом), некоторые думают наоборот, что мы не должны тратить свое время, пытаясь найти простые решения этих проблем.

Мы выяснили, как показать связь между проблемами (например, если вы знаете, как ходить в школу, вы знаете, как идти в пекарню, которая находится прямо напротив) и легко проверяемыми проблемами, которые связаны со всеми другими легко проверяемыми проблемами ( NP-complete, но давайте назовем их «ключевыми проблемами»), так что если кто-то когда-нибудь покажет, что одна из ключевых проблем легко решаема, то все проблемы, которые легко проверяемы, также легко разрешимы (то есть P = NP). С другой стороны, если кто-то показывает, что одна из ключевых проблем не может быть легко решаема, то ни одна из других проблем также не может быть легко решаема (т. Е. P <> NP).

Таким образом, этот вопрос является заманчивым и относительно важным на практике (хотя некоторые утверждают, что нам следует сосредоточиться на альтернативных определениях «простого»), и люди вкладывают в дебаты довольно много денег и времени.

Джереми
источник
1

Я немного скептически отношусь к возможности объяснить эту проблему 10-летнему, или даже непрофессионалу, без искажения ключевых понятий.

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

Антонио Валерио Мицели-Бароне
источник
Это не ответ на вопрос.
Дэйв Кларк
Почему нет? Вопрос был «Как бы вы объяснили проблему P = NP 10-летнему ребенку», и я ответил, что правильного объяснения, которое не искажает проблему, вероятно, не существует. Конечно, вы можете не согласиться с моим ответом, но почему вы утверждаете, что он не отвечает на этот вопрос?
Антонио Валерио Мицели-Бароне
3
На мой взгляд, это возможный ответ, хотя я не согласен. Это правда, что мы не можем бездумно отождествлять P с чем-то вроде «набора проблем, которые могут быть эффективно решены в реальном мире». Однако я не думаю, что это исключает возможность объяснения проблемы P =? NP десятилетний ребенок на интуитивном уровне. Например, дети десяти лет или около того изучают площадь круга. Любое строгое отношение к области требует большой осторожности, но это не исключает возможности обучения концепции области на интуитивном уровне полезным способом.
Цуёси Ито
P
1
P
1

выигрышные стратегии для различных классических настольных игр, таких как линейный или (в последнее время) видеоигры, доказали свою готовность к завершению, и это отличный способ представить / описать некоторые основные теории для новичков.

линкор как 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 - трудная экстремальная техническая статья на бумаге выше

ВЗН
источник
0

И вот мой взгляд на проблему.

Kido!

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

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

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

Поэтому такие проблемы, которые трудно решить, но если их решение легко проверить в несколько простых шагов, они называются проблемами NP.

Теперь вы спросите, что означает P = NP? На самом деле этот вопрос означает, что есть ли способ найти более простое решение для нахождения наилучшей стратегии или упорядоченного списка ходов для игры в шахматы, не используя все миллиарды возможностей, как мы делаем для простого дополнения? Этот простой вопрос еще не получен. У нас нет ни доказательств его правды, ни отвержения, но если мы это сделаем, это будет прорыв. Если это окажется правдой, наша цивилизация может решить очень сложные проблемы, превратив их в задачи класса P. Люди смогут за несколько секунд взламывать пароли, сообщения будут расшифровываться и многое другое, поэтому эта проблема считается одной из самых важных проблем тысячелетия.

Мохсин Хиджази
источник
Возможно, стоит ужесточить текст. Вы пытались прочитать это вслух?
Андрас Саламон
Я не думаю, что все должно быть затянуто как математические определения.
Мохсин Хиджази
Если вы слишком сильно затянете текст, у обычного человека не будет достаточно «пробела», чтобы понять одну концепцию, прежде чем перейти к следующей концепции.
Ян Рингроз
n×n
Эта ссылка, возможно, более понятна, чем предыдущая: cstheory.stackexchange.com/questions/6563/…
Хуан Бермехо Вега