Мне недавно напомнили о проблеме против N P, как объяснил Стивен А. Кук в Математическом институте Клея.
Это вызвало у меня интерес, и я хотел бы узнать об этом больше. Первым шагом будет более глубокое понимание проблемы и понимание области в целом.
Можете ли вы порекомендовать какие-либо книги или другие ресурсы, где я могу узнать больше о проблеме?
Ответы:
Приятно видеть такого старшекурсника с такой энтузиазмом в решении этой великой проблемы. Позвольте мне дать вам совет из моего собственного опыта.
- очень интересная проблема. Последствия ответа огромны, особенно в том случае, если два класса равны. Награда велика на многих уровнях, от альтруистического научного до материалистического денежного вознаграждения. Это побуждает многих молодых людей, которые сталкиваются с проблемой, пытаться ее решить, не имея или не имея достаточных знаний о ней.п≠ Nп
Возможно, большинство студентов-теоретиков проходят этот этап. У вас будет идея и вы думаете, что это правильно, но почти наверняка вы ошибаетесь. Некоторые люди никогда не проходят через эту фазу и смущают себя, будучи слишком упрямыми, чтобы признать свои ошибки.
В FOCS 2010 Рахул Сантанам сравнил вопрос о с мифическим монстром. Чтобы победить этого монстра, потребовалось бы много жертв и смелости. В конце концов, это может быть самой сложной проблемой когда-либо. Чтобы иметь шанс на борьбу, вам придется много изучить эту проблему и сложность в целом. Вы никогда не узнаете, какой будет «слабость монстра».п≠ Nп
Поэтому мой совет таков: не торопитесь, зная проблему. Каждый раз, когда вы найдете решение, предположите, что вы как-то не правы, и попытайтесь найти проблему с ним. Таким образом, вы многому научитесь.
Что касается ссылок, я бы также порекомендовал книгу Сипсера. После завершения я бы порекомендовал «Вычислительная сложность: современный подход» Ароры и Барака, более ориентированная на сложность книга, требующая хорошего понимания концепции вычислений.
источник
Я настоятельно рекомендую «Введение в теорию вычислений» Сипсера, особенно потому, что оно охватывает, по крайней мере, один из основных барьеров для разрешения P против NP, а именно релятивизацию. Он содержит очень четкое доказательство результата Бейкера-Гилла-Соловая. Я не уверен, содержит ли он что-нибудь о результатах Разборова-Рудича, но это фантастический, очень ясный и легко читаемый вводный ресурс для изучения не только P против NP, но и многих других смежных тем в теории сложности. ..что важно, потому что, если вы заинтересованы в решении проблемы, вам нужно иметь некоторый опыт в этой области и идеи, с чего начать.
источник
Удачи. Проблема кажется сложной. :-)
источник
источник
Классическим справочником по полноте NP является книга Гэри и Джонсона (http://tinyurl.com/2w5yofs). Это и поучительно и тщательно.
Лично я учился у Кляйнберга Тардоса (http://tinyurl.com/37dtyyl), потому что мой университет использовал его.
источник
Я бы также предложил взять экземпляр проблемы и попытаться ее решить. Это хорошая практика, чтобы экспериментировать с открытыми проблемами. Под экспериментом я подразумеваю, что вы можете писать программы или реализовывать известные алгоритмы другими и понимать, как они работают, где они терпят неудачу и т. Д. Кроме того, вы можете обнаружить несколько проверочных методов. Помните, что они не посадят вас в тюрьму, если вы будете учиться и много работать над этим и не сможете найти никакого решения. Напротив, ваш уровень компетентности гарантированно возрастет.
В большинстве случаев эти проблемы в целом труднее решить, чем их конкретные случаи . Читайте о НФЛ, чтобы получить представление.
В моем случае я был скоро похоронен под пулом идей и связанных понятий. Есть трюки программирования / кодирования и есть теоретические маневры. Например, если вы хотите решить любую проблему, используя концепции генетического алгоритма, вы скоро обнаружите, что только GA - это огромный мир, который нужно открыть! Недавно я узнал об изучении связей в GA / EA. Не знаю много об этом, хотя.
Кроме того, когда вы пытаетесь что-то кодировать, вы обнаружите, что некоторые языки / инструменты программирования лучше / проще, чем другие. Я заблудился в обсуждении того, почему Алексей Степенов считает ООП математически неправильным и в чем преимущество функционального программирования. У меня нет следа, но я хорошо помню, в начале я изучал проблему NP-Complete / Hard.
Я приветствую вас, поскольку путешествие, хотя и приключенческое!
источник
P, NP и NP-Полнота: Основы теории сложности Одеда Голдрайха были бы еще одной хорошей вводной книгой.
После вступительного содержания я хотел бы также порекомендовать « Вопрос P = NP» и «Потерянное письмо Геделя» Ричарда Дж. Липтона.
источник
Я рекомендую отличную обзорную статью Ланса Фортнау «Состояние проблемы P и NP» , в которой обсуждаются некоторые новые подходы к проблеме.
источник
источник
Ланс Фортноу недавно расширил и опубликовал свою и без того всеобъемлющую колонку из CACM (упомянутую в другом ответе М.А.) в полнометражную научно-популярную книгу «Золотой билет: P, NP и Поиск невозможного» . она была рассмотрена в газете «Йоркер» «Самая глубокая математическая проблема» Назаряном. ( страница издателей , издательство Принстонского университета)
источник