Los científicos de la computación buscan muchas verdades y respuestas: velocidades de algoritmo óptimas, avances en inteligencia artificial, pensar en cualquier palabra de moda en torno a los grandes datos y hay muchas cosas.
PERO, este esmalte comercializado solo cubre el verdadero corazón de la informática, que es mucho menos codificación y mucha MÁS lógica y deducción matemática.
Para ilustrar, hay muchos, muchos problemas en informática; Sin embargo, hay una pregunta para gobernarlos a todos, que ha llamado la atención de los geeks informáticos de todo el mundo, para reflexionar sobre una pequeña y sucinta declaración con profundas implicaciones en todo tipo de campos, y demuestra que muchos olvidan la LÓGICA inherente problemas y verdades que muchos informáticos pretenden resolver. ¿Qué es lo que preguntas? Deleitar sus ojos…
- ¿Cuáles son algunos buenos libros sobre el desarrollo matemático de la informática?
- ¿Cuál es la importancia de estudiar matemáticas discretas como informático?
- ¿Cuál sería la relación más efectiva entre las matemáticas y la programación en educación?
- Cómo mejorar mi habilidad de programación en los temas de matemática y geometría
- ¿A las personas apasionadas por las matemáticas también les encanta la codificación?
¿Está P = NP completo?
…¿Qué?
¿Qué se supone que significa ESO en el mundo?
Retrocedamos un momento y analicemos otras preguntas más básicas que tienen los científicos de la computación antes de profundizar en este tema.
Analicemos, por ejemplo, el problema del conjunto independiente.
(Tomado de mi encantador curso de introducción; si desea ver más, vaya a http://datastructur.es y vaya a las diapositivas en la última semana que detalla np-completeness)
Básicamente, es muy parecido al famoso problema de color del mapa, donde puedes intentar ver si existe una manera de asegurarte de que ningún país tenga una frontera con otro del mismo color.
Ahora, ¿por qué es un problema? Obviamente hemos visto mapas como ese, y la imagen obviamente muestra una respuesta, ¿verdad?
Bien, eso es cierto; pero ¿qué tan fácil fue dar esa respuesta? No es tan fácil, ¿eh?
Porque el hecho es que, en el nivel fundamental, los informáticos están buscando algoritmos o métodos manejables para obtener respuestas sobre si existe o no una respuesta.
Esto llega a lo que P significa en la ecuación:
Los problemas de clase P son problemas de decisión en los que estamos tratando de determinar si existe o no una respuesta en tiempo polinómico.
Estos problemas de decisión son sí o no. Por ejemplo, ¿existe una manera de colorear un mapa con cuatro colores de tal manera que no toquen dos del mismo color?
Tiempo significa cuánto tiempo toma la respuesta con respecto al tamaño de la entrada; digamos, el número de países o nodos.
Este NO es un problema de clase P, porque no hay una manera confiable de resolverlo (en el nivel básico) que no sea adivinar cada combinación, que, en probabilidad y combinaciones básicas, no se convierte en un problema polinómico, sino factorial tiempo uno.
Sin embargo, es un problema de clase NP.
NP significa que es razonablemente rápido y fácil VERIFICAR que una respuesta es verdadera.
Es como dar un mapa de solo cuatro colores y preguntar: “¿Es correcto?”. Es la diferencia entre ¿Existe una respuesta y es una respuesta correcta ?
Todos los problemas de la clase P son de clase NP, ya que obviamente si tiene un buen algoritmo para obtener una respuesta, entonces es fácil verificar que cierta combinación de coloraciones sea verdadera.
Pero, ¿qué pasa con ese término COMPLETO?
En primer lugar, vamos a otro problema interesante en informática:
El problema de la satisfacción
Básicamente pregunta si para un conjunto dado de condiciones, una combinación de valores verdadero / falso se evaluará como verdadero.
¿Porque es esto importante? Simplemente parece otro problema aleatorio.
Bueno, de hecho, el problema de satisfacción (para nosotros, tres variables, o 3-SAT) de hecho REDUCE, o es esencialmente el mismo problema que, el problema de conjunto independiente.
Este es un hecho importante, porque NP Complete es una subclase especial de problemas de NP que se reducen entre sí.
Lo que significa resolver uno, ¡los resuelves todos!
Pero, ¿por qué es esto importante de alguna manera?
Bueno, aquí hay algunas aplicaciones:
¿Puedo optimizar las rutas de mi avión para que tengan un costo inferior a $ 1B?
¿Existe una proteína con secuencia de aminoácidos X con energía potencial menor que Y?
Dado el número Z, ¿existe un par de factores primos x e y donde x * y = z?
Estos son problemas de NP que tienen respuestas obvias, pero una forma difícil de DETERMINARlos de manera confiable desde cero.
Es por eso que todos quieren saber si P = NP está completa: ¡implica que cada pregunta con respuestas obvias tiene una forma algo confiable y rápida de OBTENER esas respuestas!
Y, según Kurt Godel, esto implica que podríamos construir algoritmos para resolver y encontrar algoritmos para problemas de sí / no. Informático artificial, ¿eh? 🙂
Y, especialmente con el problema del factor principal, ¡podría crear enormes debilidades en criptografía y ciberseguridad!
Supongo que no es tan emocionante …
Pero de todos modos, también podría ganar mucho dinero, ya que muchos de los siguientes problemas pueden resolverse fácilmente si P = NP se completa:
Pero obviamente para un problema tan enorme, obviamente hay muchas más complejidades de las que tengo tiempo para explicar (o entender, eso sí).
Pero la opinión general en este momento es que NO son del mismo conjunto, que fácilmente verificable no significa fácilmente solucionable, ¡ pero aún existe la posibilidad!
Pero volviendo al punto de la respuesta, los informáticos no son solo programadores para las grandes empresas de alta tecnología. Hay tanta lógica, filosofía y matemática detrás de escena que pocos ven detrás de las luces LED, las redes sociales y la realidad virtual.
Pero incluso si estaba completamente confundido, o no podría importarle menos estos problemas, al menos ahora puede dirigirse a cualquier científico de la computación y preguntarle “Oye, ¿P = NP se completa?” Y quedarán super impresionados por su conocimiento del campo de la informática! 🙂
