¿Hay alguna intersección entre la teoría A y la teoría B?

8

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?

Robert
fuente
8
¿Podemos (como comunidad) dejar de usar estos términos completamente inútiles, por favor?
David Richerby
1
A pesar de dar una respuesta, también creo que las etiquetas no están muy bien definidas, tienen un significado más sociológico que científico y no son tan útiles.
Sasho Nikolov
1
En la primera pregunta que vincula, los autómatas se describen como Teoría A. Diría que fueron principalmente Teoría A en los años 70 u 80 (estudiados como un modelo débil de computación), pero ahora son mucho más un tema de Teoría B. O al menos, ambos son y pueden contar como una intersección natural.
Bruno
1
@DavidRicherby ¿Qué tal la teoría A y la teoría ? α
Robert Furber

Respuestas:

7

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.

Sasho Nikolov
fuente
6

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 .AQd×dAns,tQdnAns=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í .

Shaull
fuente
2

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 .

Joshua Grochow
fuente
¿Aunque quizás alguien más conocedor en el área podría agregar más referencias, como @AndrejBauer?
Joshua Grochow
O @NeelKrishnaswami?
Joshua Grochow