Los problemas de la gráfica dura de NP son los problemas que le piden un problema de decisión relacionado con alguna propiedad no trivial de una gráfica. No todas las propiedades no triviales de un gráfico conducen a problemas de NP completo. Por ejemplo: Decidir si un gráfico tiene un ciclo de Eulerian es solucionable en tiempo polinómico, mientras que Decidir si un gráfico tiene un ciclo de hamilton es un problema NP-difícil. La regla simple es: si puede reducir (eficientemente) un problema NP-hard conocido a su problema, entonces su problema es NP-hard.
Hay un montón de problemas Graph que son NP-hard. Algunos de los famosos son:
- Decidir si una gráfica tiene un ciclo hamiltoniano .
- Decidir si una gráfica G tiene una camarilla de tamaño como máximo k en ella.
- Decidir si un gráfico G tiene un conjunto independiente de tamaño como máximo k.
- Decidir si un gráfico G tiene una cubierta de vértice de tamaño como máximo k.
- Coloración gráfica.
- Encontrar el ancho del árbol para un gráfico.
Y así. La mayoría de estos pueden reducirse de 3SAT a través de reducciones muy simples. Puedes encontrar muchos otros (que me perdí) de Wikipedia.
- ¿Cuántas computadoras diferentes de las grandes empresas tienen el mismo diseño de CPU?
- ¿Cuáles son las aplicaciones de la informática afectiva en los negocios electrónicos?
- ¿La mayoría de las computadoras precompiladas admiten procesadores de diferentes marcas?
- Cómo multiplicar números de complemento a dos de punto fijo
- ¿Qué proporción de artículos de informática publicados contienen resultados no válidos?
