¿Por qué encontrar el número cromático es NP-Hard?

Sabemos que el número cromático de un grafo GRAMO es el menor número de colores necesarios para colorear los vértices de GRAMO para que no haya dos vértices adyacentes del mismo color.

Pero, ¿por qué la coloración es NP-HARD? ¿Y cuál es la diferencia entre él y la coloración de vértices?ingrese la descripción de la imagen aquí

¿Sabes lo que significa NP-Hard en términos de informática teórica? Esencialmente significa que cualquier problema en NP se puede transformar para que se convierta en el problema de encontrar el número cromático de un gráfico. ¿Y puedes definir la coloración de los vértices? Que yo sepa es lo mismo.
Sí, lo sé, pero ¿por qué este problema 'Chromatic Coloring' es NP-Hard?
Incluso determinando si el número cromático es ≤ 3 (es decir, si un gráfico dado es de 3 colores) es NP-difícil. Puede encontrar varias descripciones de la reducción estándar de CNF-SAT buscando en Google np-hard de 3 colores .
Una de las razones es que el número de colorantes que tenemos que probar crece muy, muy rápido y no tenemos una forma clara de decidir qué colorantes "vale la pena probar".
@Henning Makholm por qué es NP-Hard no NP-Complete, creo que es NP-COMPLETE
@TandeeHolwa: la capacidad de 3 colores es NP-completa. "NP-completo" significa que es tanto NP-duro como en NP (y es trivialmente obvio que la capacidad de 3 colores está en NP). Por otro lado, "calcular el número cromático" no es un problema de decisión y, por lo tanto, el concepto de NP-completo ni siquiera se aplica a él.
Entonces, ¿es eso para saber si el problema es NP-Completo o NP-Difícil, entonces si no es un problema de decisión, entonces debe ser NP-Difícil + NP-Completo? ¿O todos los problemas NP-Complete también son NP-Hard?
Todos los problemas NP-Completos son de hecho NP-Difíciles (los problemas NP-Completos son los "problemas más difíciles" de la clase NP, mientras que los problemas NP-Difíciles son "al menos tan difíciles" como los de la clase NP).

Respuestas (1)

Un problema de decisión A es NP-difícil significa que si puede resolver A en polinomio en tamaño de entrada , puede resolver cualquier problema NP en tiempo polinomial (en tamaño de entrada). El mecanismo para convertir un problema B en un problema A (en tiempo polinomial) se llama reducción de B a A.

3-COLOURABILIDAD
Entrada: Un gráfico G
Pregunta: ¿Es G 3-coloreable (es decir, es x ( GRAMO ) ≤ 3 ) ?

El problema 3-COLOURABILIDAD es NP-difícil porque hay una reducción de tiempo polinomial de 3-SAT a 3-COLOURABILIDAD y hay una reducción de SAT a 3-SAT. Está demostrado que si puedes resolver SAT en tiempo polinomial, puedes resolver cualquier problema NP en tiempo polinomial (teorema de Cook). Por lo tanto, verificar si el número cromático es como máximo 3 es difícil y, por lo tanto, encontrar el número cromático exactamente también debe ser difícil.

Nota: (Lee esto por si te interesan las rebajas)
Puedes encontrar una rebaja de NAE SAT a 3-COLOURABILITY más fácilmente (creo que sí).

La primera oración de esto se encuentra a menudo en tratamientos populares, pero es ligeramente incorrecta. Como está escrito, sería satisfecho por cualquier problema fuera de P, pero si P≠NP entonces existen problemas NP-intermedios, que por definición no están ni en P ni en NP-difícil. En cambio, la dureza NP se define explícitamente por la existencia de reducciones (poli-tiempo muchos-uno).
¿Por qué encontrar el número cromático es NP-Hard?
RespuestasAquíPolítica de privacidad1y, 0v