De Ita Luna, GuillermoDE ITA LUNA, GUILLERMO; 57559Perez Barrios, Omar2020-11-122020-11-122015https://hdl.handle.net/20.500.12371/8996“Dentro del área de ciencias de la computación se han definido gran diversidad de problemas, de los cuales se ha encontrado algoritmos para resolver gran parte de éllos. Sin embargo, conocer un conjunto de pasos para llegar a la solución de un problema no siempre es suficiente, existen algunos problemas en el área de computación en los cuales el número de operaciones que se requieren para llegar a la solución del problema aumenta mucho más rápido de lo que se incrementan los datos de entrada del problema. El estudio de estas características de un algoritmo son consideradas dentro del área de teoría de la complejidad computacional, la cual tiene sus orígenes en los inicios de la década de los 60’s, cuando los primeros usuarios de computadoras electrónicas comenzaron a prestar peculiar interés al desempeño de sus programas. Encontrar técnicas satisfactorias para resolver problemas computacionales ha eludido a investigadores por años, entre los problemas más desafiantes computacionalmente, destaca el problema de satisfactibilidad de restricciones, introducido por Stephen Arthur Cook, tras el cual se han desarrollado diversas líneas de investigación enfocadas en el campo de complejidad computacional”.pdfspaINGENIERÍA Y TECNOLOGÍAComplejidad computacionalTeoría de grafosAlgoritmosProgramación de computadorasTesis de maestríaopenAccess