2009/12/29 by Marco Pedicini, Pedicini, Marco, Mario Piazza +1
Computer Science · #Computational Complexity (cs.CC) #F.1.3 #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.CC #cs.LO
paper · pdf · doi:10.48550/arxiv.0912.5342
22 pages, 2 figures, journal submission
arxiv created 2009/12/29 · arxiv updated 2010/01/14
In this paper, we show how a construction of an implicit complexity model can be implemented using concepts coming from the core of von Neumann algebras. Namely, our aim is to gain an understanding of classical computation in terms of the hyperfinite II1 factor, starting from the class of Kalmar recursive functions. More methodologically, we address the problem of finding the right perspective from which to view the new relation between computation and combinatorial aspects in operator algebras. The rich structure of discrete invariants may provide a mathematical setting able to shed light on some basic combinatorial phenomena that are at the basis of our understanding of complexity.