NP (clase de complejidad)

En esta clase están el problema del viajante (también llamado "problema del viajante de comercio" o "problema del agente viajero") donde se quiere saber si existe una ruta óptima que pasa por todos los nodos en un cierto grafo y el problema de satisfacibilidad booleana en donde se desea saber si una cierta fórmula de lógica proposicional puede ser cierta para algún conjunto de valores booleanos para las variables.Dada su importancia, se han hecho muchos esfuerzos para encontrar algoritmos que decidan algún problema de NP en tiempo polinómico.Por lo tanto, una amplia clase de problemas en principio inconexos son reducibles unos a otros, y por lo tanto resultan en "el mismo problema" -- un resultado profundo e inesperado.Denominamos CLIQUE al siguiente problema: Dado un grafo G y un entero k, ¿es posible encontrar un subgrafo de G completo de tamaño k?Formaremos un grafo G con un nodo por cada literal que aparece en cada cláusula.