Clases NP Hard y NP-Complete
Un problema está en la clase NPC si está en NP y es tan hardcomo cualquier problema en NP. Un problema esNP-hard si todos los problemas en NP son polinomiales reducibles en el tiempo, aunque no lo sea en NP mismo.
Si existe un algoritmo de tiempo polinomial para cualquiera de estos problemas, todos los problemas en NP podrían resolverse en tiempo polinómico. Estos problemas se llamanNP-complete. El fenómeno de NP-completitud es importante tanto por razones teóricas como prácticas.
Definición de NP-Completitud
Un idioma B es NP-complete si cumple dos condiciones
B está en NP
Cada A en NP es el tiempo polinomial reducible a B.
Si un idioma satisface la segunda propiedad, pero no necesariamente la primera, el idioma B que se conoce como NP-Hard. Informalmente, un problema de búsquedaB es NP-Hard si existe alguna NP-Complete problema A que Turing reduce a B.
El problema en NP-Hard no se puede resolver en tiempo polinomial, hasta P = NP. Si se demuestra que un problema es NPC, no hay necesidad de perder el tiempo tratando de encontrar un algoritmo eficiente. En cambio, podemos centrarnos en el algoritmo de aproximación de diseño.
Problemas NP-Complete
A continuación se presentan algunos problemas NP-Complete, para los cuales no se conoce ningún algoritmo de tiempo polinomial.
- Determinar si una gráfica tiene un ciclo hamiltoniano
- Determinar si una fórmula booleana es satisfactoria, etc.
Problemas NP-Hard
Los siguientes problemas son NP-Hard
- El problema de la satisfacibilidad del circuito
- Establecer cubierta
- Cubierta de vértice
- Problema del vendedor ambulante
En este contexto, ahora discutiremos TSP es NP-Complete
TSP es NP-Complete
El problema del viajante consiste en un vendedor y un conjunto de ciudades. El vendedor tiene que visitar cada una de las ciudades partiendo de una determinada y regresando a la misma ciudad. El desafío del problema es que el viajante quiere minimizar la duración total del viaje.
Prueba
Probar TSP is NP-Complete, primero tenemos que demostrar que TSP belongs to NP. En TSP, buscamos un recorrido y comprobamos que el recorrido contiene cada vértice una vez. Luego se calcula el costo total de los bordes del recorrido. Finalmente, comprobamos si el costo es mínimo. Esto se puede completar en tiempo polinomial. AsíTSP belongs to NP.
En segundo lugar, tenemos que demostrar que TSP is NP-hard. Para probar esto, una forma es demostrar queHamiltonian cycle ≤p TSP (ya que sabemos que el problema del ciclo hamiltoniano es NPcompleto).
Asumir G = (V, E) para ser una instancia del ciclo hamiltoniano.
Por tanto, se construye una instancia de TSP. Creamos el gráfico completoG' = (V, E'), dónde
$$ E ^ {'} = \ lbrace (i, j) \ colon i, j \ in V \: \: y \: i \ neq j $$
Por lo tanto, la función de costo se define de la siguiente manera:
$$ t (i, j) = \ begin {cases} 0 & if \: (i, j) \: \ in E \\ 1 & de lo contrario \ end {cases} $$
Ahora, suponga que un ciclo hamiltoniano h existe en G. Está claro que el costo de cada borde enh es 0 en G' como cada borde pertenece a E. Por lo tanto,h tiene un costo de 0 en G'. Por tanto, si graficaG tiene un ciclo hamiltoniano, luego grafica G' tiene un recorrido por 0 costo.
Por el contrario, asumimos que G' tiene un recorrido h' de costo como máximo 0. El costo de los bordes enE' son 0 y 1por definición. Por lo tanto, cada borde debe tener un costo de0 como el costo de h' es 0. Por tanto, concluimos queh' contiene solo bordes en E.
Así hemos probado que G tiene un ciclo hamiltoniano, si y solo si G' tiene un recorrido de costo como máximo 0. TSP es NP-completo.