Complejidad computacional

Complejidad computacional
Es una rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable, comúnmente se estudia eltiempo y el espacio (memoria), pero para realizar esto primero debemos introducir la noción de problema.
La complejidad computacional considera globalmente todos los posibles algoritmos para resolver unproblema dado.
Se interesa en la distinción que existe entre los problemas que pueden ser resueltos por un algoritmo en tiempo polinomico y los problemas para los cuales no conocemos ningún algoritmopolinomico, es decir, el mejor no es polinomico.
Tiempo polinomial
Es el tiempo ideal. En computación, cuando el tiempo de ejecución de un algoritmo es menor que un cierto valor calculado,obviamente usando una formula polinomial como por ejemplo logarítmicas, lineales, cuadráticas o cubicas, se dice que dicho problema se puede resolver en un tiempo polinomico.
Los problemas matemáticos lospodemos dividir en dos grupos:
* Problemas indecidibles: Aquellos que no se pueden resolver mediante un algoritmo.
* Problemas decidibles: Aquellos que cuentan al menos con un algoritmo parasu computo. Sin embargo, un problema decidible puede no ser solucionado por un computador, porque el algoritmo requiere un número elevado de operaciones para resolverlo. Esto nos permite separar endos los problemas decidibles:
* Problemas tratables.- son los problemas que cuentan con al menos una solución polinomial.
* Problemas intratables.- un problema es intratable si no puede serresuelto por algún algoritmo eficiente. En simples palabras, los problemas que pueden ser resuelto en teoría, pero no en practica.
Clasificación por su complejidad:
Clase P: Los algoritmos decomplejidad polinómica se dice que son tratables en el sentido de que suelen ser abordados en la practica. Los problemas para los que se conocen algoritmos con esta complejidad se dice que forman la clase...