Gibt es Schnittpunkte zwischen Theorie A und Theorie B?

In den folgenden zwei Fragen Ursprünge und Anwendungen von Theorie A gegen Theorie B? und solide Anwendungen der Kategorietheorie in TCS? Viele Menschen teilten ihr Wissen und ihre Meinung über die Aufteilung dieser beiden Bereiche in theoretische CS.

Ich bin ein Student der Mathematik mit Erfahrung in Graphentheorie und Kategorietheorie, entscheidenden mathematischen Kenntnissen für Theorie A bzw. B, und ich möchte mehr lernen und wahrscheinlich sogar ernsthafte Forschung in theoretischer CS betreiben. Ich bin daran interessiert, ob es Schnittpunkte zwischen Theorie A und B gibt, und wenn ja, gibt es Personen, die an den Schnittpunkten gearbeitet haben, oder gibt es zumindest Referenzen in diesem Thema?

Ein cooles Beispiel für eine Arbeit, die sich über Dinge erstreckt, die typischerweise als Theorie A und Dinge, die typischerweise als Theorie B angesehen werden, sind die unteren Grenzen der Laufzeit des Simplex-Algorithmus mit randomisierten Schwenkregeln aufgrund von Friedmann, Hansen und Zwick . Die unteren Grenzen basieren auf unteren Grenzen für Richtlinieniterationsalgorithmen für Paritätsspiele, die ein Werkzeug sind, das in der formalen Verifikation und in der Automatentheorie verwendet wird.

$A\in {\mathbb Q}^{d\times d}$$A^n$$s,t\in \mathbb Q^d$$n$$A^ns=t$

Diese Arten von Problemen können als Erreichbarkeitsprobleme für lineare Schleifen angesehen werden, wodurch sie gut in den Bereich der formalen Verifikation, des SIG-LOG und der Theorie B fallen.

Die technische Analyse verwendet jedoch typischerweise Werkzeuge aus der Zahlentheorie, Analyse und algebraischen Berechnungen, die eher im Rahmen von Theorie A liegen.

Ein guter Ort, um darüber zu lesen, ist hier .

Soweit ich weiß, verwenden lineare Logik und "implizite Komplexitätstheorie" Werkzeuge, die häufig in Theorie B (Typentheorie, Theorie der Programmiersprachen usw.) zu finden sind, um Komplexitätsklassen zu erfassen und zu studieren. Einige dieser Arbeiten gehen auf Bellantoni & Cook zurück . In jüngerer Zeit fällt mir die Arbeit von Ugo Dal Lago ein .