Ресурсы, чтобы узнать о проблеме P против NP

12

Мне недавно напомнили о проблеме против N P, как объяснил Стивен А. Кук в Математическом институте Клея.PNP

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

Можете ли вы порекомендовать какие-либо книги или другие ресурсы, где я могу узнать больше о проблеме?

Джон Кокс
источник
Перепечатано с сайта math.stackexchange.com/questions/13742/… , который в настоящее время не имеет ответов.
Цуёси Ито

Ответы:

11

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

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

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

В FOCS 2010 Рахул Сантанам сравнил вопрос о с мифическим монстром. Чтобы победить этого монстра, потребовалось бы много жертв и смелости. В конце концов, это может быть самой сложной проблемой когда-либо. Чтобы иметь шанс на борьбу, вам придется много изучить эту проблему и сложность в целом. Вы никогда не узнаете, какой будет «слабость монстра».PNP

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

Что касается ссылок, я бы также порекомендовал книгу Сипсера. После завершения я бы порекомендовал «Вычислительная сложность: современный подход» Ароры и Барака, более ориентированная на сложность книга, требующая хорошего понимания концепции вычислений.

chazisop
источник
4
Спасибо за ваши слова мудрости. Если я полностью честен, чем больше я узнаю о проблеме, тем невозможнее найти решение. Конечно, очень интересно!
Джон Кокс
4
PvsNP
2
Кроме того, если бы она была монстром, я бы сразу же прекратил преследовать ее, потому что я ненавижу монстров :)
Мухаммед Аль-Туркистани
9

Я настоятельно рекомендую «Введение в теорию вычислений» Сипсера, особенно потому, что оно охватывает, по крайней мере, один из основных барьеров для разрешения P против NP, а именно релятивизацию. Он содержит очень четкое доказательство результата Бейкера-Гилла-Соловая. Я не уверен, содержит ли он что-нибудь о результатах Разборова-Рудича, но это фантастический, очень ясный и легко читаемый вводный ресурс для изучения не только P против NP, но и многих других смежных тем в теории сложности. ..что важно, потому что, если вы заинтересованы в решении проблемы, вам нужно иметь некоторый опыт в этой области и идеи, с чего начать.

Филип Уайт
источник
Спасибо за предложение, я получу копию из библиотеки и буду просматривать ее :)
Джон Кокс
7

PNP

Удачи. Проблема кажется сложной. :-)

Аарон Стерлинг
источник
7
кажется трудным - это сильно заниженное описание твердости P против NP. :)
Сянь-Чи Чанг 之 之
Спасибо за предложение, есть много материалов, чтобы проверить там.
Джон Кокс
7

PNP

Мухаммед Аль-Туркистани
источник
Спасибо за отличную ссылку, я буду добавлять этот мой список чтения отличных материалов, касающихся проблемы :)
Джон Кокс
4

Классическим справочником по полноте NP является книга Гэри и Джонсона (http://tinyurl.com/2w5yofs). Это и поучительно и тщательно.

Лично я учился у Кляйнберга Тардоса (http://tinyurl.com/37dtyyl), потому что мой университет использовал его.

Гаутам Камат
источник
Отлично, у меня уже есть копия книги Клиенберга Тардоса для курса, который я изучаю, и сегодня я получу книгу Гэри и Джонсона из библиотеки. Спасибо, что сообщили мне об этом.
Джон Кокс
3

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

В большинстве случаев эти проблемы в целом труднее решить, чем их конкретные случаи . Читайте о НФЛ, чтобы получить представление.

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

Кроме того, когда вы пытаетесь что-то кодировать, вы обнаружите, что некоторые языки / инструменты программирования лучше / проще, чем другие. Я заблудился в обсуждении того, почему Алексей Степенов считает ООП математически неправильным и в чем преимущество функционального программирования. У меня нет следа, но я хорошо помню, в начале я изучал проблему NP-Complete / Hard.

Я приветствую вас, поскольку путешествие, хотя и приключенческое!


источник
3

P, NP и NP-Полнота: Основы теории сложности Одеда Голдрайха были бы еще одной хорошей вводной книгой.

После вступительного содержания я хотел бы также порекомендовать « Вопрос P = NP» и «Потерянное письмо Геделя» Ричарда Дж. Липтона.

Абузер Якарылмаз
источник
Sayin Abuzer yakaryilmaz ... Вторая предложенная вами книга доступна на его сайте бесплатно.
Tayfun Pay
geekster-- думаю, что вы ошибаетесь. у него есть блог с таким же именем, но у него нет книги
vzn
2

Я рекомендую отличную обзорную статью Ланса Фортнау «Состояние проблемы P и NP» , в которой обсуждаются некоторые новые подходы к проблеме.

Марко Амнелл
источник
Спасибо, что сообщили мне об этой статье, она определенно выглядит так, что ее стоит прочитать.
Джон Кокс
2

P=?NPPNP

Александр бондаренко
источник
Спасибо за эти ссылки. Особенно интересно отметить текущие мысли и прогнозы людей с большим знанием P против NP.
Джон Кокс
2

Ланс Фортноу недавно расширил и опубликовал свою и без того всеобъемлющую колонку из CACM (упомянутую в другом ответе М.А.) в полнометражную научно-популярную книгу «Золотой билет: P, NP и Поиск невозможного» . она была рассмотрена в газете «Йоркер» «Самая глубокая математическая проблема» Назаряном. ( страница издателей , издательство Принстонского университета)

ВЗН
источник