Hay docenas de formas de representar la “notación” asíncrona (sin tiempo), todas las cuales tienen utilidad en la complejidad computacional. Algunos ejemplos incluyen: una extensión de álgebra booleana que elimina los valores de verdad 1, 0 y los reemplaza por {1 (0), 1, 0, nulo} donde generalmente hablando 1 (0) es un intermedio y nulo aún no ocurrir. También hay representaciones geométricas, gráficas y topológicas. Los circuitos, aunque son más difíciles de diseñar que sus primos síncronos (dependientes del reloj), también son bastante útiles. Las redes de Petri, o sistemas de transición de estado definidos por lugares P, transiciones T y flujos F entre P y T. En general, las simulaciones estocásticas son asíncronas, dándoles la capacidad de capturar las características de los sistemas dinámicos del mundo real. Las redes neuronales, incluida la Deep Mind de Google, utilizan métodos híbridos (por ejemplo, descenso de gradiente asincrónico) para podar un poco el espacio de fase local.
Supongo que su pregunta no se refiere a una forma específica de representar sistemas asincrónicos (si es así, comience con una lógica asincrónica), más bien supongo que quiere saber por qué los sistemas asincrónicos son útiles desde un punto de vista de complejidad. Hay mucha literatura sobre casos específicos, pero para motivarme, ofreceré lo siguiente: debido a la calidad “libre de tiempo”, existe una aleatoriedad inherente en los sistemas asincrónicos que se puede aprovechar para lograr un cálculo supra-terante. Dicho de otra manera, si tomamos un método determinista, digamos EDO continuas, que se están completando, encontramos que no pueden resolver problemas no recursivos. En contraste, cualquiera de los métodos antes mencionados puede resolver estos mismos problemas no recursivos. El truco es la naturaleza inherentemente aleatoria, que esencialmente puede modificarse para dar una especie de oráculo para una máquina clásica de turing. Mucha gente piensa que esta es al menos parte de la razón por la cual los cerebros humanos tienen una ventaja sobre el silicio síncrono.