La foto de la portada es una imagen de libre uso de Pixabay y editada por 
Estas tres áreas tradicionalmente centrales de la teoría de la computación, vienen vinculadas con la siguiente pregunta:
Desde entonces, los avances tecnológicos han aumentado enormemente nuestra capacidad de cálculo y han sacado esta cuestión del ámbito de la teoría para llevarla al mundo de la práctica.
Inicaremos hablando de estás áreas en orden inverso, ya que es posible que si empezamos por el final se puede entender mejor la razón del principio.
Imagen de Pixabay y editada por
Por ejemplo, el problema de ordenación es fácil.
Digamos que hay que ordenar una lista de números en orden ascendente. Incluso un pequeño ordenador puede ordenar un millón de números con bastante rapidez.
Digamos que hay que encontrar un horario de clases para toda la universidad que satisfaga algunas restricciones razonables, como que no haya dos clases en la misma sala a la misma hora.
El problema de la programación parece mucho más difícil que el de la ordenación. Si sólo tiene mil clases, encontrar el mejor horario puede requerir siglos, incluso con un supercomputador.
Sorprendentemente, no sabemos la respuesta, aunque se ha investigado intensamente durante los últimos 60 años.
En uno de los logros importantes de la teoría de la complejidad hasta ahora, es que los investigadores han descubierto un elegante esquema para clasificar los problemas según su dificultad computacional.
Utilizando este esquema, podemos demostrar un método para dar pruebas de que ciertos problemas son computacionalmente difíciles, aunque no podamos demostrar que lo son.
Imagen de Pixabay y editada por
Si te gusto este tema y quieres seguir profundizando acerca de La Teoría de la Computación, no te pierdas la próxima publicación, pero si aún así deseas conocer otra perspectiva del mismo, te invito a investigar en las siguientes referencias que acá te comparto:
