¿Puede una maquina actualmente resolver problemas complejos?

La respuesta es que, difícilmente.

Primero acotemos que son problemas complejos, utilizando la informática.

Un problema complejo es aquel no determinista resuelto en tiempo polinomial.

Dada una lista de nombres, se nos pide que la ordenemos en descendiente. A más nombres el tiempo necesario para ordenarlo será lineal y la función necesaria seria la misma.Este problema requiere el mismo tiempo, para la misma maquina o persona, por cada parte de trabajo que se añada. 10 nombres 10 segundos, 100 nombres = 10*100 segundos.

Por el contrario un problema como el de resolver un sudoku, una matriz NxM necesita un tiempo T y una función O. Una matriz N⁹xM⁹ por el contrario necesita un numero de veces de “relleno y comprobación” exponencialmente superior al problema P inicial (relleno de nombres). En un sudoku tu función es optimizar la matriz dadas las letras del juego para que al final el panel este completo, pero si ponemos 9 millones de columnas y 9 millones de filas, podríamos necesitar miles de años en resolver con la misma maquina, por lo que el problema es complejo. Dadas mil P, o maquinas o personas en paralelo que se hablen entre ellas no resolvería el problema.

Problemas complejos y solvencia.

La mayoria de problemas NP-completos (“non deterministic polynomial time“) del tipo humano, tienen un espacio de estados discreto exponencialmente enorme conforme el problema crece. Por ejemplo, en el problema del agente comercial (donde el comercial debe visitar una serie de puntos de visita en una ciudad sin pasar por el mismo sitio) el espacio de estados es el numero de permutaciones y la funcion objetiva de un estado particular (permutacion) es la suma de las distancias de los vertices consecutivos durante el viaje del agente comercial.

470px-hamiltonian_path-svg
Camino Hamiltoniano. Optimización del comercial

Lo que los ingenieros informáticos tratan de desarrollar es un algoritmo para que puedas tener garantías de resolución como “para cada caso de este problema, el algoritmo dará una solución que sera 2 veces peor que la solución mas optima del problema”. Por peor, en este caso me refiero a que la función objetiva devuelta por el algoritmo dará un resultado 2 veces menor al mínimo de la función objetiva que se pueda conseguir.

Aprendizaje de maquinas.

Echemos un vistazo a lo que el aprendizaje de máquinas te puede ofrecer. La mayoría de conceptos de aprendizaje de maquina se puede entender como “aproximación” o probabilista, tal y como nuestro cerebro funciona, hablando rápido. Dados unos pares de datos (entradas, salidas), lo que esperas es encontrar una función que dadas las entradas te devuelva una salida aproximada a la deseable en la mayoría de los casos.

Por lo tanto, el objetivo en los problemas NP-completos el objetivo esta en conseguir un algoritmo, mientras la maquina de aprendizaje te de una función. No son lo mismo pero puedes pensar que un algoritmo es una función. Por ejemplo todos los algoritmos de ordenar palabras toman una ristra desordenada y la devuelve ordenada. Quizá no tengas información de tu nuevo algoritmo creado por una maquina, pero si cumple la tarea en P (tiempo polinomial) es que va todo bien.

Para finalizar, tenemos el siguiente problema con nuestra maquina pensadora. Le damos a nuestra maquina de aprendizaje un conjunto de pares de datos (entradas, salidas) para el problema NP-completo. Por ejemplo, para el problema del agente comercial, las entradas serian los grafos vacíos, y las salidas serian los viajes por la ciudad optimizados. La maquina devuelve algo, que es un nuevo gráfico. Necesitaríamos modelar nuestro problema de tal forma que tenga restricciones para que la salida sea un viaje valido para el agente comercial. Suponiendo que lo hace, la maquina toma un grafo vacío de vértices y te diseña un viaje optimizado.

Resumiendo, el estado actual del aprendizajee de maquina y los objetivos de optimización, no nos ayuda mucho a resolver problemas NP-completos.

Anuncios