17 votos

¿Cuáles son NP-completos, los problemas y por qué son tan importantes?

Sigo escuchando las preguntas acerca de si algo es NP-completo, pero en realidad nunca hablar de lo que es. ¿Por qué a la gente le importa mucho acerca de NP-completo los problemas?

19voto

Can Berk Güder Puntos 661

Un problema está en la clase NP si la solución puede ser verificado en el polinomio de tiempo, es decir, si la dimensión del problema es n usted puede estar seguro de que por lo suficientemente grande n necesita menos de r·nk operaciones para comprobar la solución.

Un problema está en la clase P, si la solución puede ser encontrado en el polinomio de tiempo, lugar. Un problema en P está en NP, por definición, pero a la inversa puede no ser el caso; probablemente la más importante pregunta abierta en ciencias de la computación es si las clases P y NP son los mismos, que es P=NP.

NP-completo es una familia de NP problemas para los cuales usted sabe que si uno de ellos tenía un polinomio solución, a continuación, cada uno de ellos tiene.

(EDITADO) Por el momento, sólo se conoce de algoritmos para NP-completo los problemas se exponencial en el número de operaciones, por lo que no están prácticamente resueltos para n grande.

15voto

prakash Puntos 18075

Para ampliar Mau la respuesta, usted debe preocuparse acerca de la NP-complete problemas porque hay una familia entera de ellos, que abarca un gran número de aparentemente algoritmos básicos a través de una amplia gama de disciplinas. No se trata de ocultar los problemas, pero es muy importante y muy práctico preguntas. Por ejemplo, considere la siguiente:

  • El problema del viajante - encontrar la ruta más corta (en un gráfico) que te permite visitar cada ciudad exactamente una vez.
  • Bin packing problema - hay un número fijo (entero) tamaño de los recipientes y objetos de diferentes tamaños. Minimizar el número de contenedores necesarios para mantener todos los objetos
  • Mochila problema - objetos de diferentes tamaños y valores, y una mochila con un fijo de enteros de tamaño, seleccione los objetos que puede caber adentro con el valor de la mayoría de
  • Mínimo Vértice de la cubierta - encontrar el más pequeño conjunto de vértices tales que cada arista contiene al menos un vértice elegido
  • Clique - encontrando que el grupo más grande de personas que conocemos todos
  • Subgrafo isomorfismo - hace un gráfico que contiene un subgrafo isomorfo a otro?
  • Embalaje - dado un número de series, ¿cuál es el número máximo de conjuntos disjuntos que puede ser seleccionado? Esto está relacionado con el conjunto de la cubierta, donde estamos tratando de elegir los conjuntos de manera que cada elemento está dentro de al menos un conjunto
  • Subconjunto suma - Dado un conjunto de números enteros, ¿ algún subconjunto suma a 0?

A pesar de que muchos de estos problemas pueden parecer abstractos, muchos de los problemas más complicados no puede ser resuelto de manera eficiente con las técnicas actuales, como son el equivalente a uno de estos.

El problema de NP integridad ha recibido una gran cantidad de atención. Una vez que haya reducido un problema NP-completo, usted sabe renunciar a un eficiente algoritmo rápido y empezar a buscar en aproximaciones.

6voto

Michiel de Mare Puntos 15888

Cualquier problema que una solución (una vez encontrado) puede ser rápidamente verificado como una solución que se dice ser " NP" (Aquí, "rápidamente" significa en el polinomio de tiempo). Cualquier problema que una solución puede ser encontrar rápidamente se dice que "en P." P es un subconjunto de NP - es decir, cualquier problema que una solución puede ser rápidamente encontró también puede ser rápidamente verificado.

Un problema es NP-completo si es el más difícil problema en NP. Sorprendentemente, hay muchas NP-completo los problemas, que son todos equivalentes - aquí, equivalente significa que una rápida (polinomio de tiempo) solución a cualquiera de ellos podría dar una solución rápida a todos los demás. También sorprendentemente, una solución rápida a cualquier tipo NP-completo problema también podría darnos una solución rápida a cualquier problema en NP.

Por lo que hay un rápido (polinomio de tiempo) algoritmo para resolver NP-completo los problemas? Que es la P=NP problema, uno de los grandes problemas no resueltos de nuestro tiempo. Sin embargo, la mayoría de cuerda mathemeticians creo (y espero!) que P≠NP, porque probando matemáticas-teoremas es NP-Completo, por lo que si P=NP, estaríamos fuera de un puesto de trabajo! :)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by: