2015/02/04 by Thomas Seiller, Seiller, Thomas
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Operator Algebras (math.OA)
paper · pdf · doi:10.48550/arxiv.1502.01257
openalex publication_date 2015/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We explain how recent developments in the fields of realisability models for linear logic -- or geometry of interaction -- and implicit computational complexity can lead to a new approach of implicit computational complexity. This semantic-based approach should apply uniformly to various computational paradigms, and enable the use of new mathematical methods and tools to attack problem in computational complexity. This paper provides the background, motivations and perspectives of this complexity-through-realisability theory to be developed, and illustrates it with recent results.