Hacemos una verificación profunda cada post de nuestra página web con la meta de enseñarte siempre la información veraz y certera.
Solución:
Un problema pertenece a la clase NP si su solución puede ser verificado en tiempo polinomial, es decir, si la dimensión del problema es n, puede estar seguro de que para n suficientemente grande necesita menos de r · nk Operaciones para verificar la solución.
Un problema pertenece a la clase P si su solución puede ser encontrado en tiempo polinomial, en cambio. Un problema en P está en NP por definición, pero lo contrario puede no ser el caso; probablemente la pregunta abierta más importante en informática es si las clases P y NP son iguales, es decir, P=NP.
NP-completo es una familia de problemas NP para los que sabes que si uno de ellos tiene una solución polinomial, entonces cada uno de ellos posee.
(EDITADO) Por el momento, solo los algoritmos conocidos para NP-completo Los problemas son exponenciales en número de operaciones, por lo que prácticamente no se pueden resolver para n grande.
Para ampliar la respuesta de Mau, debe preocuparse por los problemas NP completos porque existe una familia completa de ellos que abarca una gran cantidad de algoritmos aparentemente básicos en una amplia gama de disciplinas. Estos no son problemas oscuros, sino preguntas extremadamente importantes y muy prácticas. Por ejemplo, considere lo siguiente:
- Problema del vendedor ambulante: encontrar el camino más corto (en un gráfico) que le permita visitar cada ciudad exactamente una vez.
- Problema de embalaje en contenedores: hay varios contenedores de tamaño fijo (entero) y objetos de diferentes tamaños. Minimice la cantidad de contenedores necesarios para contener todos los objetos
- Problema de la mochila: dados objetos de varios tamaños y valores y una mochila con un tamaño entero fijo, elija los objetos que puedan caber dentro con el mayor valor
- Cobertura mínima de vértices: encontrar el conjunto más pequeño de vértices de modo que cada borde contenga al menos un vértice elegido
- Camarilla: encontrar el grupo más grande de personas que se conocen entre sí
- Isomorfismo de subgrafo: ¿un gráfico contiene un subgrafo isomorfo a otro?
- Empaquetado de conjuntos: dado un número de conjuntos, ¿cuál es el número máximo de conjuntos disjuntos que se pueden seleccionar? Esto está relacionado con la cobertura del conjunto, donde intentamos elegir conjuntos para que cada elemento esté dentro de al menos un conjunto.
- Suma de subconjuntos: dado un conjunto de enteros, ¿algún subconjunto suma 0?
Aunque muchos de estos problemas pueden parecer abstractos, muchos problemas más complicados no se pueden resolver de manera eficiente con las técnicas actuales, ya que son equivalentes a uno de estos.
El problema de la completitud de NP ha recibido una gran cantidad de atención. Una vez que haya reducido un problema a NP-completo, sabrá que debe renunciar a un algoritmo rápido y eficiente y comenzar a buscar aproximaciones.
Cualquier problema para el cual una solución (una vez encontrada) pueda ser rápidamente verificado como solución se dice que está “en notario público(Aquí, “rápidamente” significa en tiempo polinomial). Cualquier problema para el cual se puede encontrar una solución encontrado rápidamente se dice que está “en PAG.” PAG es un subconjunto de notario público – es decir, cualquier problema para el que se pueda encontrar una solución rápidamente encontrado también puede ser rápido verificado.
un problema es NP-completo si es el problema más difícil en notario público. Sorprendentemente, hay muchos NP-completo problemas, que son todos equivalentes – aquí, equivalente significa que una solución rápida (en tiempo polinomial) para cualquiera de ellos le daría una solución rápida para el resto. También algo sorprendente, una solución rápida a cualquier NP-completo problema también le daría una solución rápida a ninguna problema en notario público.
Entonces, ¿hay un algoritmo rápido (tiempo polinomial) para resolver NP-completo ¿problemas? Ese es el problema P=NP, uno de los mayores problemas sin resolver de nuestro tiempo. Sin embargo, la mayoría de los matemáticos cuerdos creen (¡y esperan!) que P≠NPporque demostrar teoremas matemáticos es NP-Completo; Así que si P=NP¡Nos quedaríamos sin trabajo! 🙂