En las siguientes dos preguntas ¿ Orígenes y aplicaciones de la teoría A contra la teoría B? y aplicaciones sólidas de teoría de categorías en TCS? , muchas personas compartieron sus conocimientos y opiniones sobre la división de esas dos áreas en CS teórica.
Soy un estudiante de matemáticas con experiencia en teoría de grafos y teoría de categorías, conocimiento matemático crucial para la teoría A y B, respectivamente, y estoy buscando aprender más y probablemente incluso hacer una investigación seria en CS teórica. Estoy interesado en saber si hay intersecciones entre la teoría A y B, y si es así, ¿hay alguna persona que haya trabajado en las intersecciones o al menos hay alguna referencia en este tema?
Respuestas:
Un buen ejemplo de trabajo que abarca las cosas que generalmente se consideran la teoría A y las cosas que generalmente se consideran la teoría B son los límites inferiores en el tiempo de ejecución del algoritmo simplex con reglas pivotantes aleatorias, debido a Friedmann, Hansen y Zwick . Los límites inferiores dependen de los límites inferiores para los algoritmos de iteración de políticas para juegos de paridad, que son una herramienta utilizada en la verificación formal y la teoría de autómatas.
fuente
Un ejemplo (de mi campo de investigación) es el análisis de sistemas dinámicos: en un sistema dinámico (lineal), se le da una matriz y razona sobre varias propiedades de . Por ejemplo, el problema de la órbita de Kannan-Lipton pregunta, dados dos vectores , si existe tal que .A ∈ Qre× d UNAnorte s , t ∈ Qre norte UNAnortes = t
Estos tipos de problemas pueden considerarse problemas de accesibilidad para bucles lineales, que los ubican bien en el dominio de la verificación formal, SIG-LOG y Theory B.
Sin embargo, el análisis técnico generalmente usa herramientas de teoría de números, análisis y cálculos algebraicos, que están más dentro del alcance de la Teoría A.
Un buen lugar para comenzar a leer sobre esto es aquí .
fuente
Según tengo entendido, la lógica lineal y la "teoría de la complejidad implícita" utilizan herramientas que a menudo se encuentran en la Teoría B (teoría de tipos, teoría de lenguajes de programación, etc.) para capturar y estudiar clases de complejidad. Parte de este trabajo se remonta a Bellantoni & Cook . Más recientemente, me viene a la mente el trabajo de Ugo Dal Lago .
fuente