¿Cuáles son los problemas NP?

Question

Me leyó el artículo en la wikipedia, pero no podía entender por qué son exactamente los problemas NP. ¿Puede alguien decirme acerca de ellos y también lo es la relación de ellos con P Problemas?

Answer 1

problemas NP son problemas que dada una solución propuesta, se puede verificar la solución en un tiempo polinómico. Por ejemplo, si usted tiene una lista de los cursos de la Universidad y la necesidad de crear una programación para que los cursos no entrará en conflicto, sería una tarea muy difícil (en cuanto a la complejidad). Sin embargo, dada una propuesta de calendario, usted puede fácilmente verificar su exactitud.

Otro ejemplo importante desde el campo de la encriptación: dado un número que es el resultado de multiplicar dos números primos muy grandes, es muy difícil encontrar esos números primos basadas únicamente en el resultado. Sin embargo, dos números, es muy fácil de comprobar la solución (multiplicar ellos, comparar).

He eligió intencionadamente ejemplos que se encuentran en NP y no en P (es decir, un problema que son difíciles de encontrar la solución para) para que pueda entender la diferencia. Todos los problemas que son fáciles de resolver, también son fáciles de verificar - acaba de resolver y comparar. Es decir, P es un subconjunto de NP.

Answer 2

No es realmente una respuesta, porque el vínculo de Piccolo es más útil, pero afirma un investigador de HP haber probado P! = NP, aquí está el papel.

www.hpl.hp.com/personal/Vinay_Deolalikar/Papers /pnp12pt.pdf

No fue aceptado todavía, pero le deseo buena suerte para el 1M $.