Podemos reducir 3-Coloring (un problema NP-complete muy conocido) a la programación. Esto mostrará que la programación también está completa para NP (ya que sabemos que está en NP).
La reducción es así:
Supongamos que se nos da una gráfica [matemática] G (V, E) [/ matemática] donde los vértices son un conjunto de clases y una arista [matemática] (u, v) \ en E [/ matemática] representa un alumno [matemática ] s_ {uv} [/ math] que quiere tomar ambas clases. Ahora considere esto como una instancia de un problema de programación en el que estamos tratando de colocar cada clase en 3 franjas horarias diferentes (los tres colores) donde ningún estudiante tiene un mal horario (dos o más clases se superponen).
Et voila! Si tenemos una forma polinómica de resolver la programación, entonces tenemos una forma polinómica de resolver 3 colores. Por lo tanto, la programación es NP-completa.
- ¿Cuál es el mejor camino a seguir como estudiante de primer año para ingresar a la especialidad de CS?
- ¿Para qué sirve un bus de expansión en la arquitectura de bus?
- ¿Qué cosas debería uno estudiar para ganar las competencias de codificación de Codechef o TopCoder?
- ¿Cómo se transmitirán los datos en el microprocesador?
- ¿Será Econometrics o Machine Learning más importante en el futuro?
