Recursos para aprender sobre el problema P vs. NP

12

Hace poco me recordaron el problema vs. como lo explicó Stephen A. Cook en el Clay Mathematics Institute.N PPNP

Ha despertado mi interés y me gustaría aprender más al respecto. El primer paso sería obtener una comprensión más profunda del problema y una comprensión del área en general.

¿Me puede recomendar libros u otros recursos donde pueda aprender más sobre el problema?

Jon Cox
fuente
Cruzado desde math.stackexchange.com/questions/13742/… , que actualmente no tiene respuestas.
Tsuyoshi Ito

Respuestas:

11

Es bueno ver a un compañero de pregrado en la búsqueda de este gran problema, con tanto entusiasmo. Permítame ofrecerle un consejo de mis propias experiencias.

PNP es un problema muy interesante. Las implicaciones de la respuesta son inmensas, especialmente en el caso de que las dos clases sean iguales. La recompensa es excelente en muchos niveles, desde el científico altruista hasta el premio materialista de dinero. Eso lleva a muchos jóvenes que encuentran el problema al tratar de resolverlo, sin conocimiento o con un conocimiento limitado.

Quizás la mayoría de los estudiantes de teoría pasan por esa fase. Tendrá una idea y pensará que es correcta, pero es casi seguro que está equivocado. Algunas personas nunca pasan por esa fase y se avergüenzan de ser demasiado tercas para admitir sus errores.

En FOCS 2010, Rahul Santhanam comparó la pregunta con un monstruo mítico. Se necesitarían muchos sacrificios y valor incluso para tratar de derrotar a este monstruo. Después de todo, puede ser el problema más difícil de todos. Para tener una oportunidad de pelear, tendrás que estudiar mucho sobre este problema y la complejidad en general. Nunca sabrás cuál será la "debilidad del monstruo".PNP

Así que mi consejo es el siguiente: tómese su tiempo para conocer el problema. Cada vez que encuentre una solución, asuma que está equivocado de alguna manera e intente encontrar el problema. De esa manera aprenderás mucho.

En cuanto a las referencias, recomendaría también el libro de Sipser. Después de terminarlo, recomendaría "Complejidad computacional: un enfoque moderno" de Arora y Barak, un libro más orientado a la complejidad, que requiere una buena comprensión del concepto de computación.

chazisop
fuente
44
Gracias por tus sabias palabras. Si soy completamente honesto, cuanto más aprendo sobre el problema, más imposible le parece a alguien encontrar una solución. ¡Ciertamente muy interesante sin embargo!
Jon Cox
44
+1 Me gusta, pero déjame estar en desacuerdo. no es un monstruo, sino una niña muy hermosa que espera que alguien levante su velo para que el mundo pueda disfrutar de su gloriosa belleza. Además, ella es muy inocente y pura y solo está tratando de jugar con nosotros y provocarnos con sus rompecabezas todo el tiempo ...PvsNP
Mohammad Al-Turkistany
2
Además, si ella fuera un monstruo, inmediatamente dejaría de perseguirla porque odio a los monstruos :)
Mohammad Al-Turkistany
9

Sugiero encarecidamente la "Introducción a la teoría de la computación" de Sipser, particularmente porque cubre al menos una de las principales barreras para resolver P vs. NP, a saber, la relativización. Contiene una prueba muy clara del resultado de Baker-Gill-Solovay. No estoy seguro si contiene algo sobre los resultados de Razborov-Rudich, pero es un recurso introductorio fantástico, muy claro y fácil de leer para aprender no solo sobre P vs. NP sino también para muchos otros temas relacionados en la teoría de la complejidad. ... lo cual es significativo porque si su interés es tratar de resolver el problema, querrá tener algunos antecedentes en el campo e ideas sobre dónde comenzar.

Philip White
fuente
Gracias por la sugerencia, recibiré una copia de la biblioteca y la revisaré :)
Jon Cox
7

PNP

Buena suerte. El problema parece ser difícil. :-)

Aaron Sterling
fuente
77
parece ser difícil es una descripción muy subestimada de la dureza de P vs NP. :)
Hsien-Chih Chang 張顯 之
Gracias por la sugerencia, hay una buena cantidad de materiales para revisar.
Jon Cox
7

PNP

Mohammad Al-Turkistany
fuente
Gracias por un excelente enlace, agregaré mi lista de lecturas de materiales excelentes relacionados con el problema :)
Jon Cox
4

La referencia clásica para completar NP es el libro de Garey y Johnson (http://tinyurl.com/2w5yofs). Es a la vez instructivo y minucioso.

Personalmente, aprendí de Kleinberg Tardos (http://tinyurl.com/37dtyyl), porque mi universidad lo usó.

Gautam Kamath
fuente
Excelente, ya tengo una copia del libro de Klienberg Tardos para un curso que hago, y más tarde hoy recibiré el libro de Garey y Johnson de la biblioteca. Gracias por hacérmelo saber.
Jon Cox
3

También sugeriría tomar una instancia del problema e intentar resolverlo. Es una buena práctica experimentar con problemas abiertos. Por experimento quiero decir, puede escribir programas o implementar algoritmos conocidos por otros y comprender cómo funcionan, dónde fallan, etc. Además, puede descubrir varias técnicas de prueba. Recuerde, no lo meterán en la cárcel si estudia y trabaja mucho en esto y no puede encontrar ninguna solución. Por el contrario, su nivel de competencia está garantizado para aumentar.

En la mayoría de los casos, estos problemas en general son difíciles de resolver que sus instancias específicas . Lea sobre la NFL para tener una idea.

En mi caso, pronto me enterraron bajo un grupo de ideas y conceptos relacionados. Hay ajustes de programación / codificación y hay maniobras teóricas. Como por ejemplo, si desea resolver cualquier instancia de problema utilizando conceptos de Algoritmo Genético, pronto descubrirá, ¡GA solo es un vasto mundo por descubrir! Recientemente he llegado a saber sobre Linkage Learning en GA / EA. Sin embargo, no sé mucho al respecto.

Además, cuando intente codificar las cosas, encontrará que algunos lenguajes / herramientas de programación son mejores / más fáciles que otros. Me perdí en la discusión de por qué Alex Stepenov piensa que la POO es matemáticamente incorrecta y cuál es la ventaja de la programación funcional. No tengo el rastro, pero recuerdo claramente que al principio estaba estudiando un problema NP-Complete / Hard.

¡Te doy la bienvenida, ya que el viaje es aunque aventurero!


fuente
3

P, NP y NP-Completeness: The Basics of Complexity Theory de Oded Goldreich sería otro buen libro introductorio.

Después de los contenidos introductorios, me gustaría recomendar también The P = NP Question y Gödel's Lost Letter de Richard J. Lipton.

Abuzer Yakaryilmaz
fuente
Sayin Abuzer yakaryilmaz ... El segundo libro que sugirió está disponible en su sitio web de forma gratuita.
Tayfun paga el
Geekster-- Creo que estás equivocado. tiene un blog con el mismo nombre pero no tiene el libro
vzn
2

Recomiendo el excelente artículo de revisión de Lance Fortnow, "El estado del problema P versus NP" , que analiza algunos enfoques nuevos del problema.

Marko Amnell
fuente
Gracias por informarme sobre este artículo, definitivamente parece que vale la pena leerlo.
Jon Cox