Un ejemplo concreto de un problema computacionalmente complejo que se resuelve en la naturaleza es encontrar viajes aéreos asequibles .
Para un viaje en avión determinado, diga un vuelo LHR-ORD el 5 de noviembre, dado un conjunto de tarifas que se han presentado en cada mercado, los precios adjuntos a esas tarifas y la disponibilidad en cada segmento, calculando la combinación de tarifas más barata disponible que hace ese viaje ocurre en algún lugar entre NP difícil, EXPSPACE difícil e indecidible, dependiendo de las restricciones que impongas al problema; ver discusión en “La complejidad computacional de la planificación de viajes aéreos” de Carl de Marcken, http: //static.googleusercontent…. .
Durante los últimos diez años, ITA Software ha utilizado computadoras cotidianas para brindar soluciones útiles a este problema en aproximadamente una décima de segundo. Este es un ejemplo de un escenario del mundo real donde los problemas con la complejidad computacional aterradora se pueden resolver de maneras útiles.
- Si los números constructivos positivos también pueden tender al infinito, entonces, ¿dónde están los otros tipos de números irracionales positivos en la recta numérica?
- ¿Cómo dibuja una línea en la pantalla un programa de gráficos por computadora? Del código de alto nivel al nivel de la tarjeta gráfica, ¿qué sucede?
- ¿Cómo podría el aprendizaje automático o la IA en general ayudar a la agricultura?
- ¿Cuál es tu libro de texto de aprendizaje automático favorito?
- ¿Aplicaciones de inteligencia artificial para finanzas?
Puede ser muy, muy frustrante para alguien que entiende la complejidad computacional ver una pregunta como “¿cuánto tiempo le toma a una computadora promedio de 2012 encontrar una solución para un problema de NP?”
Esto se debe a que esta pregunta es más o menos lo mismo que preguntar ” ¿cuánto dura un trozo de cuerda? ” Quiero decir, puedo responder a esa pregunta, pero tendrá que decirme sobre la cantidad de cuerda que tiene.
Del mismo modo, si va a preguntar “¿cuánto tiempo tarda una computadora en responder un problema de NP?” Lo primero que voy a preguntar es “¿cuántos datos tienes?” Resolver el problema de la mochila no es tan difícil si solo hay 5 cosas que pueden entrar en la mochila, pero es más difícil si hay mil millones de cosas. La clase de complejidad NP no es única a este respecto: los problemas en P son iguales. Encontrar el máximo común divisor de cinco números es más rápido que encontrar el máximo común divisor de cinco mil millones de cosas.
