prucommercialre.com


¿Qué es la Teoría de la Complejidad Computacional?

Teoría de la complejidad computacional es un área de matemáticas y ciencias de la computación que se ocupa de los recursos necesarios para resolver problemas en un sistema informático. Un número de técnicas disponibles para determinar las necesidades de recursos de un problema. Algunos problemas pueden no ser factible en los sistemas informáticos existentes, debido a sus demandas de recursos. Los investigadores clasifican los problemas de dificultad y se pueden dividir en los cálculos polinomio (P) frente polinómicas nonterministic (NP) problemas.

Resolver un cálculo requiere recursos tales como tiempo, espacio de almacenamiento y hardware. Un sistema informático puede tener limitaciones que hacen que un problema funcionalmente imposible de resolver, ya que no cuenta con los recursos disponibles. Como la tecnología informática mejora, un problema sin solución previamente podría llegar a ser solucionable con la ayuda de las nuevas tecnologías y la investigación en el campo de la teoría de la complejidad computacional. La solvencia de un problema no se determina necesariamente por su complejidad, pero en los algoritmos utilizados para resolverlo.

En teoría de la complejidad computacional, un problema P es uno que puede ser resuelto en tiempo polinómico con un algoritmo sencillo. Todavía podría requerir recursos sustanciales, pero es tanto soluble y comprobable por ordenador. Estos problemas podrían ser considerados como rápidamente solucionables, siempre y cuando un equipo tiene los recursos disponibles para manejar los cálculos necesarios.

NP problemas son más complejos. No es posible aplicar un algoritmo único, y puede ser que sea necesario el uso de opciones más avanzadas, tales como máquinas de Turing paralelas que pueden explorar varias opciones. El problema podría ser solucionable esta manera, pero requerirá muchos más recursos. Estos problemas podrían ser más fácil para los operadores humanos que son capaces de pensar lógica avanzada, debido a que el punto de inflexión es a menudo una de la lógica más que dificultad computación pura. El problema del viajante de comercio, en el que el objetivo es encontrar la ruta más eficiente entre varias ciudades a lo largo de una ruta, es un ejemplo clásico de un problema NP en teoría de la complejidad computacional.

Clasificación de P frente a los problemas de NP a través de la teoría de la complejidad computacional puede ser una tarea compleja, y los problemas podría cambiar hacia atrás y adelante a través de la brecha. Un pequeño conjunto de problemas informáticos no se adaptan en una u otra categoría y, a veces se clasifican como tampoco con el fin de reflejar esto. Se podría eventualmente ser posible desarrollar un algoritmo para resolver un problema NP, y en algunos casos, se podría aplicar a otros problemas que tienen una estructura similar. En otros, sin embargo, podría ser un problema específico. El proceso de exploración de este tipo de programas y el desarrollo de enfoques para resolverlos es una importante área de las matemáticas y la informática que contribuye al desarrollo de los sistemas informáticos avanzados, de alta potencia.

  • Teoría de la complejidad computacional es un área de matemáticas y ciencias de la computación que se ocupa de los recursos necesarios para resolver problemas en un sistema informático.