Dos partes de TCS son algoritmos y complejidad. Voy simplista decir que los algoritmos es el estudio de los límites superiores, lo que demuestra que se puede hacer algo (con recursos restringidos, dados), y la complejidad se trata de demostrar que usted no puede hacerlo sin algunos recursos mínimos.
Muy a menudo se plantea un problema algorítmico en un modelo de decisión para ubicarlo en una clase de complejidad.
Pero algo que siempre me molestó es que algunos algoritmos elementales nunca se mencionan directamente como pertenecientes a una clase en particular. Un ejemplo es la clasificación (de comparación). Por más que lo intente, una clase relevante simplemente parece demasiado deficiente (realmente, ¿es solo verificar en el espacio de registro que el resultado está ordenado? Eso simplemente parece demasiado débil, o no estoy obteniendo la versión de decisión correcta).
¿Cuál es la clase de complejidad mejor / más apropiada / más útil en la que se encuentra la clasificación comparativa?
Creo que FP es lo que estás buscando.
fuente