2020/01/31 by Thomas Seiller, Seiller, Thomas · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.2002.00009
openalex publication_date 2020/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
In a recent paper, the author has shown how Interaction Graphs models for linear logic can be used to obtain implicit characterisations of non-deterministic complexity classes. In this paper, we show how this semantic approach to Implicit Complexity Theory (ICC) can be used to characterise deterministic and probabilistic models of computation. In doing so, we obtain correspondences between group actions and both deterministic and probabilistic hierarchies of complexity classes. As a particular case, we provide the first implicit characterisations of the classes PLogspace (un-bounded error probabilistic logarithmic space) and PPtime (unbounded error probabilistic polynomial time)