Esto dependería en gran medida de la estructura de la “categoría” de algoritmos en los que está trabajando.
Por ejemplo, uno podría imaginar una categoría de algoritmos donde los morfismos se definen del algoritmo A al B si existe un algoritmo C tal que para cualquier cadena de entrada x, A (C (x)) = B (x) (es decir, los morfismos son Reducciones de Turing).
Por otro lado, podría definir el morfismo como el anterior, excepto que el algoritmo C debe ejecutarse en el tiempo que es una función polinómica del tamaño de entrada, o utilizar un espacio logarítmico en el tamaño de la entrada (estos morfismos serían Reducciones de Karp o reducciones de espacio de registro).
- ¿Qué temas (en matemáticas y TCS) debe sobresalir un estudiante de matemáticas para seguir la teoría de la complejidad computacional?
- ¿Por qué el problema P = NP es el "gran problema" en la complejidad computacional?
- ¿Qué problemas abiertos en matemáticas tendrían aplicaciones prácticas inmediatas si se resolvieran?
- Para los usuarios, ¿se está volviendo Facebook más valioso, útil y digno de más tiempo invertido o menos? ¿Por qué? ¿Hay alguna evidencia de Facebook de que la Ley de Metcalfe es cierta (para n usuarios, el valor de la red aumenta en nxn)?
- ¿Cuáles son los tiempos de ejecución de varios algoritmos de aprendizaje automático como SVM, redes neuronales, etc. en términos de notación big-O?
Para construir una categoría completamente diferente, también se podría eliminar el algoritmo C por completo y definir los morfismos de modo que existan si y solo A (x) = B (x) para cada x. Esta sería una categoría bastante aburrida, pero sin embargo es una opción legítima.
tl; dr la cuestión de cuándo dos algoritmos son isomórficos depende mucho de la manera en que intentas clasificar tus algoritmos; No existe una opción canónica que funcione independientemente del contexto.
